codefoeces EDU186 D[组合数学] E[贪心]

设所有盒子的总和为 sum 人数为n 则一定会经过sum/n轮 并且前sum%n个人会再进行一次

这道题如果最后构成了一个合法的方案 那么一定有：

1.最多的人的盒子内的个数不超过sum/n+1

那么就变成了一道组合数学的问题 我们先找出所有的人的和 然后计算出上限 判断有无人多余上限 多的话就不合法 如果不存在超过上限的情况 那么将所有刚好等于sum/n+1的人排在前面 他们的整体位置不能改变但是相对位置可以改变 记录刚哈后等于sum/n+1的人数为c 他们是不能碰0盒子的

有sum/n+1次的数字有sum%n个 那么还剩下sum%n-c个名额 那么我们先算出前c个数字的全排列 然后再算后面的数字的全排列即可

第一次全排列 b个位置中出c个人即可 剩下的全排列把剩余位置全部占领即可

#include <bits/stdc++.h> using namespace std; const int N=55,mod=998244353; long long a[N]; void solve(){ int n;cin>>n; long long sum=0; for(int i=0;i<=n;i++){ cin>>a[i]; sum+=a[i]; } int A=sum/n +1; int c=0,d=n,b=sum%n; long long ans=1; for(int i=1;i<=n;i++){ if(a[i]>A){ans=0;cout<<0<<'\n';return;} if(a[i]==A)++c,--d; } while(c--)ans=ans*b%mod,b--; b+=n-(sum%n); while(d--)ans=ans*b%mod,b--; cout<<ans<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;cin>>t; while(t--)solve(); return 0; }

E

贪心 每个人都有基础花销和额外花销 首先将所有人的基础花销减去 然后每个人有一个额外花销 那么我们先用礼盒 尽可能的去掉高额外花销的人 然后再花剩下的钱 优先满足额外花销最小的人 这样得到的结果最大

代码变量解释： a[]存储礼盒 升序排序 b[]存储每个礼盒能够解决的花销 st存储不能用礼盒解决人的额外花销

我们每一个人分配给刚好能用礼盒解决的最小礼盒 如果没有那么就分配给结尾 也就是m+1 这样每个人只会被分配一次 然后我们从小到大遍历每个气球 然后将这个气球能解决的所有的花销都放入集合中 这样以来 由于升序 任何一个当前放出的气球 都可以解决当前集合中的所有人的 花销 那么我们选择一个最大的即可 这样的收益最大 处理完每个气球后 我们再考虑花钱即可

#include <bits/stdc++.h> using namespace std; const int N=2e5+5; typedef long long ll; long long a[N]; vector<ll>b[N]; void solve(){ long long n,m,k;cin>>n>>m>>k; for(int i=1;i<=m;i++){ cin>>a[i]; }sort(a+1,a+1+m); for(int i=1;i<=m+1;i++)b[i].clear(); multiset<ll>st; long long ans=0; for(int i=1;i<=n;i++){ long long x,y,z;cin>>x>>y>>z; k-=y; //减去基本花销 int p=lower_bound(a+1,a+1+m,x)-a; //寻找可以满足的第一个礼盒 如果没有就返回结尾+1 b[p].push_back(z-y);//将每个花销分配给第一个能满足他的礼盒 }//遍历所有的礼盒以及结尾+1 因为有些无法通过满足的人被分配给了m+1 for(int i=1;i<=m+1;i++){ for(int j:b[i])st.insert(j); //将分配给当前礼盒的放出来 当前的气球一定可以解决所有的已经放出来的人 那么我们选择一个最大的即可 这样最大化利益 if(i<=m&&!st.empty()){ auto o=prev(st.end());//取一个花销最大的出来 然后消除掉 ++ans; st.erase(o); } } for(int i:st){ //花钱满足额外消费尽量少的 if(k>=i)k-=i,ans++; } cout<<ans<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;cin>>t; while(t--)solve(); return 0; }