题目大意
有 \(n\) 个读者,第 \(i\) 年他们要一起读 \(k_i\) 本书,每一本书至少要让一个人读,每一个人也只能读恰好一本书。 如果某一个人 \(j\),如果有 \(a_j\) 个人这一年里和他读了同一本书,那么他就会感到满足。
对于所有的 \(q\) 组询问,每组给定一个 \(k_i\),求感到满足的人数的最大值。
\(\text{Solution}\)
我们先将 \(a_i\) 排序,考虑到答案一定是一个前缀 \([1,x]\),不然我们可以交换两个人 \(i \in [1,x]\) 和 \(j \in [x+1,n]\),这样显然不会更劣。
考虑设计一个状态 \(f_i\) 表示前 \(i\) 个人最多可以读 \(f_i\) 本书,且读这 \(f_i\) 本书的人都感觉满足。
转移是很简单的,\(f_i=\max\{f_{i-1},f_{i-a_i}+1\}\)。
接下来考虑怎么对于每一组询问求出答案。
既然答案是一个前缀,那么我们考虑二分这一个前缀,接下来的问题转化为:我们怎么判定前缀 \([1,x]\) 是否合法。
首先我们贪心的想,我们让后面的 \(n-x+1\) 个人每人读一本书。
接下来分为两种情况:
- 如果后面人数有剩余,那么我们让他们和 \([1,x]\) 中的读统一本书,再判定即可。
- 如果书有剩余 \(r\) 本,考虑检查 \(f_{x-a_x}\) 是否 \(\geq c\),如果是则我们让前 \(x-a_x\) 个人中不满足的和 \([x-a_x+1,x]\) 中的人读同一本即可。
代码实现很简单。
#include<bits/stdc++.h>
#define fi first
#define se second
#define vc vector
#define db double
#define END exit(0)
#define pb push_back
#define mk make_pair
#define ll long long
#define PI pair<int,int>
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define err cerr << " -_- " << endl
#define debug cerr << "------------------------" << endl
//useful:
//#define cout cerr
//#define OccDreamer
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0;char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(ll x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(ll x){write(x);putchar(32);}
inline void eprint(ll x){write(x);putchar(10);}
}using namespace IO;
const int inf=1e9;
const int MAXN=4e5+5;
const int mod=998244353;
int n, k;
int a[MAXN], f[MAXN];
inline bool judge(int x, int k){
int c=n-x, rest=c-k;
if(rest>=0 && x+rest<a[x]) return 0;
if(rest>=0) return 1;
k-=c;
if(a[x]>x) return 0;
if(f[x-a[x]]>=k) return 1;
return 0;
}
inline void solve(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+1+n); f[0]=0;
for(int i=1;i<=n;++i){
if(a[i]>i) f[i]=f[i-1];
else{
f[i]=f[i-a[i]]+1;
}
f[i]=max(f[i-1],f[i]);
}
int q=read(), k, l, r, mid;
while(q--){
k=read();
l=1, r=n;
int c;
while(l<=r){
mid=(l+r)>>1;
if(judge(mid,k-1)) l=mid+1;
else r=mid-1;
}
eprint(r);
}
return ;
}
int main(){
solve();
return 0;
}
标签:本书,return,int,题解,CF1793E,mid,long,Marketing,define
From: https://www.cnblogs.com/OccasionalDreamer/p/18012078