Problem - 1172A - Codeforces(思维+模拟)

题目大意:有 2 n 2n 2n张牌,其中有 n n n张牌是 n n n的排列,剩余 n n n张牌是 0 0 0,现在将牌打乱平分成两份,你可以将自己手上的牌放在另一堆牌的牌顶,然后拿走牌底的牌,求最少需要多少次这样的 *** 作,能让牌堆形成一个递增序列.

解题思路:先考虑最坏的情况,最坏的情况就是先把手上的 0 0 0全部打出去,然后把对应的数字牌全部收回,再依次的放,这样次数是 2 n 2n 2n.然后我们考虑把一张牌放到对应位置所需要的花费.
如果一张牌在牌堆 b b b中满足, b i < i b_i 如果一张牌不能只通过前进来满足条件的话,就必须先回到手牌中,然后再放到对应的位置,这样对应的花费就是 i + n − b i + 1 i+n-b_i+1 i+n−bi​+1.
得知这两种花费之后,我们去模拟这个过程即可.

#include
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 2e5+5;
int a[N], b[N], pos[N], cnt[N];
int main(){
    syncfalse
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i)cin>>a[i];
    for (int i = 1; i <= n; ++i){
        cin>>b[i];
        if (b[i]>0)pos[b[i]]=i;
    }
    for (int i = 1; i <= n; ++i){
        if (pos[i]cnt[i])cnt[i]=pos[i]+n-i+1;  //当前必须先回手才能进行下一步 *** 作.
            if (ans					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714058.html