cf 1463D. Pairs（差分数组，暴力思维）

题目链接：https://codeforces.ml/contest/1463/problem/D

题意：给定一个长度n(n<=2e5)的数组a(1<=a<=2*n)，然后要求出满足选x组中的最小值，n-x组中的最大值，使满足所取得的集与a相同。(这n组中的2*n个数构成一个全排列)。

题解：比如a=1 4 5 9 10.剩下b=2 3 6 7 8

第一步-贪心+暴力打表：

x=0,b=2 3 6 7 8；
x=1,b=8 2 3 6 7;
x=2,b=7 8 2 3 6;
x=3,b=6 7 8 2 3;
x=4,b=3 6 7 8 2;
x=5,b=2 3 6 7 8;

第二步-优化（找规律）：

用线隔开：左边a[i]<b[i]，右边需要满足a[i]>b[i]

x=0,b=|2 3 6 7 8；
x=1,b= 8|2 3 6 7;
x=2,b= 7 8|2 3 6;
x=3,b= 6 7 8|2 3;
x=4,b= 3 6 7 8|2;
x=5,b= 2 3 6 7 8|;

找规律：|的上方和下方均是递减的。然后接着规律就明显了，第i隔位置满足条件的所有x一定在以‘|’为中心的两边，然后差分数组一下就出来了。注意需要特判一下x=n。

总结：希望我下次做题就朝着正确的方向想，不要因为这样想有一点困难，或者是没有按照原来的思路，就，轻易放弃了一条成为好人的路。

代码：

#include <bits/stdc++.h>

#define ld double
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define rep(i,a,n)  for(ll i=a;i<=n;i++)
#define per(i,n,a)  for(ll i=n;i>=a;i--)
#define dbg(x) cout << #x << "===" << x << endl
#define dbgg(l,r,x) for(ll i=l;i<=r;i++) cout<<x[i]<<" ";cout<<"<<<"<<#x;cout<<endl
typedef long long ll;
using namespace std;

template<class T>void read(T &x){T res=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){res=(res<<3)+(res<<1)+c-'0';c=getchar();}x=res*f;}
inline void print(ll x){if(x<0){putchar('-');x=-x;}if(x>9)print(x/10);putchar(x%10+'0');}
const ll maxn = 4e5 + 10;
const ll mod = 1e9+7;

ll n,a[maxn],b[maxn],mi[maxn],mx[maxn],c[maxn],d[maxn];
ll v[maxn],id[maxn];
int main() {
    ll _s = 1;
    read(_s);
    //freopen("testdata.in","r",stdin);
	//freopen("testout.out","w",stdout);
    for (ll _=1;_<=_s;_++) {
		// dbg(_);
        read(n);
		rep(i,0,2*n) a[i]=b[i]=c[i]=d[i]=mi[i]=mx[i]=v[i]=id[i]=0;
        rep(i,1,n) read(a[i]),v[a[i]]=1,id[a[i]]=i;
        ll cnt=0,ml=0,mr=1e18;
		rep(i,1,2*n){
			if(v[i]==0) b[++cnt]=i;
			else{
				mx[i]=min(cnt,id[i]);
				mi[i]=min(n-cnt,n-id[i]);
				ll l=(id[i]-1)-mx[i]+1;
				ll r=id[i]+mi[i]-1;
				ml=max(ml,l),mr=min(mr,r);
				// cout<<"lr"<<" "<<l<<" "<<r<<endl;
				// c[l]++,c[r+1]--;
			}
		}
		// rep(i,0,n-1) c[i]+=c[i-1];
		// dbgg(0,n-1,c);
		ll ans=0;
		// rep(i,0,n-1){
			// if(c[i]==n) ans++;
		// }
		// dbg(ml),dbg(mr);
		ans=max(mr-ml+1,0ll);
		ans+=1;
		rep(i,1,n){
			if(a[i]>b[i]){
				ans-=1;break;
			}
		}
		cout<<ans<<endl;
    }
    return 0;
}

最后

以上就是内向鼠标为你收集整理的cf 1463D. Pairs（差分数组，暴力思维）的全部内容，希望文章能够帮你解决cf 1463D. Pairs（差分数组，暴力思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。