C. Nauuo and Cards （贪心、思维）

Bertha 。 2021-07-16 18:53 391阅读 0赞

[题目][Link 1]

思路：首先想能不能在原有的b中出现\* \* \* \* 1 2 3 … k，如果可以的话则利用b中原有的再添上前面的即可构成1 2 3 …n，但这个构成有一个限制，对于每一个从k往后添加k+1 k+2 … n一定要连贯着一次性达成，如果中间出现k+x没取的到，要再从前面取几个用0做缓冲，则该顺序一定会混入0，方案作废。  
剩下的情况，则看一个b数组中最多需要额外多取几个才能在用到该数时能放到底部，例如 n=6 b:0 0 2 5 6 3 对于第3个元素5，想要取到其需额外先取次数 = 3 - 4（5前面会先输出4个数，所以能少额外取4个），对于第二个元素2 想要取到其需额外先取次数= 2 - 1（2前面会先输出1个数）最终结果为max(额外输出)+n

Code:

#include<iostream>
    typedef long long ll;
    using namespace std;
    const int Max = 1e6 + 5;
    int a[Max], b[Max];
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)cin >> a[i];
    	for (int i = 1;i <= n;i++)cin >> b[i];
    	int begin = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		if (b[i] == 1)begin = i;
    		else if (begin)
    		{ 
    			if ((b[i] - 1) != i - begin)begin = 0;
    		}
    	}
    	int g = 0, mi = 0;
    	if (begin)g = n - begin + 1;
    	int f = 0;
    	if (g)
    	{ 
    		for (int i = 1;i + g <= n;i++)
    		{ 
    			if (b[i] == 0)continue;
    			int v = max(0, i - (b[i] - g - 1));
    			if (v > 0) f = 1;
    			mi = max(mi, v);
    		}
    	}
    	if(f==0&&g) cout << mi + n - g << endl;
    	else
    	{ 
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (b[i] == 0)continue;
    			int v = max(0, i - (b[i] - 1));
    			mi = max(mi, v);
    		}
    		cout << n + mi << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1173/problem/C