xg
题意
给相同长度为n的两个数组a，b。其中包括1-n和n个0。
一次操作：可以把a中任意一个数放到b的最右面，然后把b的最前面一个数放到a中。
问最少多少次操作可以使得b数组为1，2，3.....n。
思路
很明显a数组不影响结果，只需要分析b数组即可。且最多只需要2*n次操作。
如果1-n都在a中，则只需要n个操作。
如果1在b末尾，且其余数在a中，则需要n-1。（如果存在一些数在b的1的前部分，则需要判断当需要放这个数到b的末尾的时候，这个数是在a中还是b中）。
1：如果1在a中，则结果一定大于n，因为一定要把这n个数塞到b中。则只需要判断b数组中不为0的数（假如说是bi）在塞了bi个数的时候能不能从b中取出。即找Σ（0，i-（bi-1))。
2：如果1在b中。则根据1往后能否自成一段单独判断，其余类似模拟即可。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> // #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define sp ' ' #define endl ' ' #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl #define P pair<int, int> #define fi first #define se second #define pb(x) push_back(x) #define ppb() pop_back() #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define rep(i,a,b) for(int i=a;i<=b;i++) #define repd(i,a,b) for(int i=a;i>=b;i--) #define sca3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define sca2(a,b) scanf("%d %d",&(a),&(b)) #define sca(a) scanf("%d",&(a)); #define sca3ll(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c)) #define sca2ll(a,b) scanf("%lld %lld",&(a),&(b)) #define scall(a) scanf("%lld",&(a)); using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a, ll b, ll mod){ll sum = 1;while (b) {if (b & 1) {sum = (sum * a) % mod;b--;}b /= 2;a = a * a % mod;}return sum;} const double Pi = acos(-1.0); const double epsilon = Pi/180.0; const int maxn = 2e5+10; int a[maxn],b[maxn]; int main() { //freopen("input.txt", "r", stdin); int n; sca(n); int pos = n+1; rep(i,1,n) sca(a[i]); rep(i,1,n) { sca(b[i]); if(b[i]==1) pos = i; } int flag = 0,nub = n-pos+1,ans1; if(pos == n+1){ int tmp = 0; rep(i,1,n){ if(b[i] == 0) continue; tmp = max(tmp,i-b[i]+1); } printf("%d ",n+tmp ); return 0; } // bug; int cnt = 0; flag = 0; rep(i,pos,n){ if(b[i] != ++cnt){ flag =1; break; } } if(flag == 1){ int tmp = 0; rep(i,1,n){ if(b[i] == 0) continue; tmp = max(tmp,i-b[i]+1); } printf("%d ",n+tmp ); } else if(flag == 0){ int tmp = 0; rep(i,1,pos-1){ if(b[i] == 0) continue; if(i > b[i]-(n-pos+1)-1) { tmp = 1;break; } //tmp = max(tmp,i-b[i]+1); } if(tmp == 1) { printf("%d ",n+pos ); } else printf("%d ",pos-1 ); } }