4 6 2 5 8 1 3 7
Citim n. n=8. Intrăm în for. i=1. (1<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=4. st=1, dr=cnt=0. (1>0=>st>dr). Nu intrăm în while (nu s-a respectat condiția). (1>0=>st>cnt). Intrăm în al doilea if (s-a respectat condiția). a[++cnt]=a[0+1]=a[1]=x=4. Postincrementăm i.
(2<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=6. st=1, dr=cnt=1. (1=1=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+1)/2=2/2=1. (4<6=>a[1]<6=>a[m]<x). Intrăm în primul if (s-a respectat condiția). dr=m-1=1-1=0. (1=1=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[1]=x=6. Postincrementăm i.
(3<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=2. st=1, dr=cnt=1. (1=1=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+1)/2=2/2=1. (6>2=>a[1]≥2=>a[m]≥x). Nu intrăm în primul if (nu s-a respectat condiția). Intrăm în else. st=m+1=1+1=2. (2>1=>st>cnt). Intrăm în al doilea if (s-a respectat condiția). a[++cnt]=a[1+1]=a[2]=x=2. Postincrementăm i.
(4<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=5. st=1, dr=cnt=2. (1<2=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1. (6>5=>a[1]≥5=>a[m]≥x). Nu intrăm în primul if (nu s-a respectat condiția). Intrăm în else. st=m+1=1+1=2. (2=2=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[1]=x=5. Postincrementăm i.
(5<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=8. st=1, dr=cnt=2. (1<2=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1. (5<8=>a[1]<8=>a[m]<x). Intrăm în primul if (s-a respectat condiția). (1<2=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[1]=x=8. Postincrementăm i.
(6<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=1. st=1, dr=cnt=2. (1<2=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1. (8>1=>a[1]≥1=>a[m]≥x). Nu intrăm în primul if (nu s-a respectat condiția). Intrăm în else. st=m+1=1+1=2. (2=2=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[2]=x=1. Postincrementăm i.
(7<8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=3. st=1, dr=cnt=2. (1<2=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1. (8>1=>a[1]≥2=>a[m]≥x). Nu intrăm în primul if (nu s-a respectat condiția). Intrăm în else. st=m+1=1+1=2. (2=2=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[2]=x=3. Postincrementăm i.
(8=8=>i≤n). Continuăm for-ul (s-a respectat condiția). Citim x. x=7. st=1, dr=cnt=2. (1<2=>st≤dr). Intrăm în while (s-a respectat condiția). m=(st+dr)/2=(1+2)/2=3/2=1. (8>7=>a[1]≥7=>a[m]≥x). Nu intrăm în primul if (nu s-a respectat condiția). Intrăm în else. st=m+1=1+1=2. (2=2=>st≤cnt). Nu intrăm în al doilea if (nu s-a respectat condiția). Intrăm în else. a[st]=a[2]=x=7. Postincrementăm i.
(9>8=>i>n). Ieșim din for (s-a terminat condiția).
#include <bits/stdc++.h>
using namespace std;
int n , x , a[100001] , cnt;
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i++)
{
cin >> x;
int st = 1 , dr = cnt;
while(st <= dr)
{
int m = (st + dr) / 2;
if(a[m] < x) dr = m - 1;
else st = m + 1;
}
if(st > cnt) a[++cnt] = x;
else a[st] = x;
}
cout << cnt;
}
Comentarii
Trimiteți un comentariu