The Preliminary Contest for ICPC Asia Nanjing 2019——F. Greedy Sequence（贪心）

╰半夏微凉° 2024-04-18 08:19 67阅读 0赞

You’re given a permutation aaa of length n (1≤n≤105).  
For each i∈∈\[1,n\], construct a sequence sis\_isi by the following rules:

1.si\[1\]=i;  
2.The length of si is n, and for each j∈\[2,n\], si\[j\]≤si\[j−1\];  
3.First, we must choose all the possible elements of si from permutation a. If the index of si\[j\] in permutation aaa is pos\[j\], for each j≥2, ∣pos\[j\]−pos\[j−1\]∣≤k (1≤k≤105). And for each si, every element of si must occur in aaa at most once.  
4.After we choose all possible elements for si, if the length of si is smaller than nnn, the value of every undetermined element of si is 0;  
5.For each si, we must make its weight high enough.

Consider two sequences C=\[c1,c2,…cn\] and D=\[d1,d2,…,dn\], we say the weight of C is higher than that of D if and only if there exists an integer kkk such that 1≤k≤n, ci=di for all 1≤i<k, and ck>dk.

If for each i∈\[1,n\], ci=di, the weight of CCC is equal to the weight of D.

For each i∈\[1,n\], print the number of non-zero elements of si separated by a space.  
It’s guaranteed that there is only one possible answer.

Input  
There are multiple test cases.  
The first line contains one integer T(1≤T≤20), denoting the number of test cases.  
Each test case contains two lines, the first line contains two integers nnn and k (1≤n,k≤105), the second line contains nnn distinct integers a1,a2,…,an (1≤ai≤n) separated by a space, which is the permutation a.

Output  
For each test case, print one line consists of nnn integers ∣s1∣,∣s2∣,…,∣sn∣ separated by a space.  
∣si∣ is the number of non-zero elements of sequence sis\_isi.  
There is no space at the end of the line.

样例输入  
2  
3 1  
3 2 1  
7 2  
3 1 4 6 2 5 7

样例输出  
1 2 3  
1 1 2 3 2 3 3

题解 ：贪心  
首先利用滑动窗口 和set计算出 比 a\[i\]小的最大的数，存到pre数组中。  
利用贪心，从第一个数开始计算 ans【i】=ans\[  pre\[i\] \] +1;  
上式的意思是 ，计算第i个序列第一个数是i，那么比 i 小的 最大的数 就是pre【i】, ans\[ pre\[i\] \]在前面已经算过，在加上它本身就是这个序列的个数  
例如 ： ans【5】=3 代表 S5 的个数为3，pre【6】=5 表示比6小的最大的数为 5 ，那么ans【6】=ans【 pre【 6 】 】+1 =3+1=4；  
从1计算到 n就是满足条件的答案。

#include<iostream>
    #include<set>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef  long long ll;
    const int maxn=1e6+10;
    ll a[maxn],pre[maxn],ans[maxn];
    int  main()
    {
    	ll t;
    	cin>>t;
    	while(t--)
    	{
    		memset(a,0,sizeof(a));
    		memset(pre,0,sizeof(pre));
    		memset(ans,0,sizeof(ans));
    		ll n,k;
    		cin>>n>>k;
    		for(int i=1;i<=n;i++) 
    		{
    			cin>>a[i];
    		}
    		ll l=1,r=min(k+1,n);
    		set<ll> s; 
    		for(int i=1;i<=r;i++)
    			s.insert(a[i]);
    		for(int i=1;i<=n;i++)
    		{
    			while(r-i<k&&r+1<=n)  s.insert(a[++r]);//right
    			while(i-l>k) s.erase(a[l++]);//left
    			//cout<<"l "<<l<<"r "<<r<<endl;
    			set<ll>::iterator it=s.lower_bound(a[i]);
    			cout<<*it<<endl;
    			if(it==s.begin()) pre[a[i]]=0;
    			else pre[a[i]]=*(--it); 
     		}	
    // 		for(int i=1;i<=n;i++)
    // 		{
    // 			cout<<pre[i] <<"  ";
    //		 }
    //		 cout<<endl;
    		 ans[0]=0;
    		 ans[1]=1;
    		for(int i=1;i<=n;i++)
    		{
    			ans[i]=ans[pre[i]]+1;
    		}
    		for(int i=1;i<=n;i++)
    		{
    			if(i==1)
    				cout<<ans[i];
    			else
    				cout<<" "<<ans[i];
    		}
    		cout<<endl;
    	}
    	return 0;
     }