Codeforces Round 1095 (Div. 2) 补题

C. Mental Monumental (Easy Version)

自己的思路：打表发现一个数的余数可以是 [ 0 , (x-1)/2 ] U {x}，维护一个suf数组去二分答案，但是发现无法兼顾两种贡献方式，遂没写出来

两种贡献：
1.x

2.[0,(x-1)/2]

正解：在二分ck中维护一个suf以及st数组，将两种贡献方式分开，一个数如果x在0到mid，那么就留一个当x，剩下的充当第二种贡献，如果大于x，那么直接扔去当第二种一个都不需要给x自己留

留一个x本质是一种贪心：肯定越大的数越不好凑越稀有，那么x按第一种贡献肯定比第二种要优

上代码！：

#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; const int mod=1e9+7; typedef pair<int,int>pii; const int N=3e5; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int num[N],inv[N];//阶乘以及阶乘的逆元 //ans=num[a]*inv[a-b]%mod*inv[b]%mod; int kmi(int a,int b){ int res=1; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; } return res; } void init(){ num[0]=1,inv[0]=1; for(int i=1;i<=2e5;i++){//预处理出2e5内的阶乘以及其逆元 num[i]=num[i-1]*i%mod; inv[i]=kmi(num[i],mod-2); } } void solve(){ int n;cin>>n; vector<int>cnt(n+10),a(n+10); for(int i=1;i<=n;i++){ cin>>a[i]; } auto ck=[&](int mid)->bool{ vector<int>st(n+10),suf(n+10); for(int i=1;i<=n;i++){ if(a[i]<=mid&&!st[a[i]]) st[a[i]]=1; else suf[min(mid,max(0LL,(a[i]-1)/2))]++; } int need=0; for(int i=n-1;i>=0;i--) suf[i]+=suf[i+1]; for(int i=mid;i>=0;i--){ if(st[i]) continue; need++; if(need>suf[i]) return 0; } return 1; }; int l=0,r=n-1; int ans=0; while(l<=r){ int mid=l+r>>1; if(ck(mid)) l=mid+1,ans=mid; else r=mid-1; } cout<<ans+1; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T=1;cin>>T; while(T--){ solve(); cout<<endl; } return 0; }