Răspuns :
Aici poti folosi o smecherie, si anume:
1. Banuiesc ca ai un vector cu inaltimile persoanelor, daca nu ai iti faci.
2. Presupunem ca daca se deschide o noua casa, ultimii X oameni de la coada initiala se vor duce la noua casa, iar acesti X oameni sunt in ordine crescatoare a inaltimii. Sa dau un exemplu:
Oameni: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5
Cand se deschide casa noua ar pleca de la coada initiala ultimii 4 oameni, adica 2 3 4 5, si astfel noua casa are oameni in ordine crescatoare a inaltimii, pentru ca daca ar pleca mai multi, spre exemplu 5 oameni, am lua si acel 5 din fata lui 2 si omul cu inaltime 2 nu ar mai vedea.
Deci pentru coada ce care spuneam initial: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5
Ar trebui sa se deschida case cam asa:
Casa 1: 2 3 4 5
Casa 2: 1 2 3 4 5
Casa 3: 2 3
Iar la casa initiala ar ramane doar 1 2 3 4 care sunt ok ordonati.
Deci ar trebui sa deschida 3 case.
Acum sa observam o treaba: Daca oamenii sunt se la inceput ordonati crescator dupa inaltime atunci nu e nici o problema, problema apare cand avem un om mai inalt in fata unui om mai mic, adica un numar mai mare in fata unui numar mai mic. In cazul ala avem nevoie de o noua casa.
Asa ca tu poti pur si simplu sa parcurgi vectorul si sa verifici cate numere au un "om mai inalt"(numar mai mare) in fata lor si deci nu pot vedea. Asta o faci cu un simplu contor si cu in if in acel for. DUpa ce ai parcurs vectorul, acel contor e raspunsul tau!
1. Banuiesc ca ai un vector cu inaltimile persoanelor, daca nu ai iti faci.
2. Presupunem ca daca se deschide o noua casa, ultimii X oameni de la coada initiala se vor duce la noua casa, iar acesti X oameni sunt in ordine crescatoare a inaltimii. Sa dau un exemplu:
Oameni: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5
Cand se deschide casa noua ar pleca de la coada initiala ultimii 4 oameni, adica 2 3 4 5, si astfel noua casa are oameni in ordine crescatoare a inaltimii, pentru ca daca ar pleca mai multi, spre exemplu 5 oameni, am lua si acel 5 din fata lui 2 si omul cu inaltime 2 nu ar mai vedea.
Deci pentru coada ce care spuneam initial: 1 2 3 4 2 3 1 2 3 4 5 2 3 4 5
Ar trebui sa se deschida case cam asa:
Casa 1: 2 3 4 5
Casa 2: 1 2 3 4 5
Casa 3: 2 3
Iar la casa initiala ar ramane doar 1 2 3 4 care sunt ok ordonati.
Deci ar trebui sa deschida 3 case.
Acum sa observam o treaba: Daca oamenii sunt se la inceput ordonati crescator dupa inaltime atunci nu e nici o problema, problema apare cand avem un om mai inalt in fata unui om mai mic, adica un numar mai mare in fata unui numar mai mic. In cazul ala avem nevoie de o noua casa.
Asa ca tu poti pur si simplu sa parcurgi vectorul si sa verifici cate numere au un "om mai inalt"(numar mai mare) in fata lor si deci nu pot vedea. Asta o faci cu un simplu contor si cu in if in acel for. DUpa ce ai parcurs vectorul, acel contor e raspunsul tau!
#include<bits/stdc++.h>using namespace std;ifstream in("input.txt");ofstream out("output.txt");typedef long long ll;typedef string str;typedef char chr;#define save1 in.close()#define save2 out.close()#define bs bitset#define opt1 ios_base::sync_with_stdio(0)#define opt2 cin.tie(0)#define opt3 cout.tie(0)#define fi first#define se second#define vi vector<int>#define pii pair<int,int>#define pil pair<int,ll>#define pli pair<ll,int>#define pll pair<ll,ll>#define MP make_pair#define pb push_backint main(){int n,i,x,y,ans=1;opt1;opt2;opt3;cin>>n>>y;for(i=1;i<n;++i) {cin>>x; if(x<y)++ans; y=x;}cout<<ans;save1;save2;return 0;}
Vă mulțumim că ați ales să vizitați site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți alte întrebări sau aveți nevoie de asistență suplimentară, nu ezitați să ne contactați. Vă așteptăm cu drag să reveniți și nu uitați să ne salvați în lista de favorite!