网站域名空间费用,学网站开发要下载哪些软件,现在 做网站 最流行,公司网站建设介绍题目链接#xff1a;题目
大意#xff1a;
给出若干种卡片#xff0c;每种卡片有一定数量#xff0c;你可以加入不超过 k k k张任意已给出种类的卡片#xff0c;使得它们可以被分成若干组#xff0c;每组容量一定#xff0c;且同组内不存在相同种类的卡片#xff0c;…题目链接题目
大意
给出若干种卡片每种卡片有一定数量你可以加入不超过 k k k张任意已给出种类的卡片使得它们可以被分成若干组每组容量一定且同组内不存在相同种类的卡片求出最大能成立的容量。
思路
这题的两个关键点在于一找到可以分配成功的条件二正确处理各种变量的关系。 这个条件乍一看有点复杂单看每一组不知道要装什么数字那么先关注一些必要条件首先所有卡片的总和要整除每组的容量并且每种卡片的卡牌数量都不能超过组数否则由于抽屉原理肯定会存在有卡片没地方装被迫和自己兄弟挤在一起。这时候你发现这些就是充分条件想象你把每种卡片尽可能地放在不同组中一层层地放满后一定能够成立不会有冲突。 接着我们得到条件就是 s u m % l 0 sum\%l0 sum%l0且单种卡片最大数量 m a x s u m / l maxsum/l maxsum/l如何把 k k k加入其中呢请看代码。 一开始不敢写是因为以为卡片数量总和超过long long后来发现最多可能也就到1e16long long是9e18
代码
#include bits/stdc.h
using namespace std;#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pairint,int
#define vec vectorvoid solve(){int n, k;cin n k;vecint a(n 1);for(int i 1; i n; i){cin a[i];}int mx *max_element(a.begin(), a.end());int sum accumulate(a.begin(), a.end(), 0ll);int ans 0;for(int l n; l 1; l--){if(sum % l 0 mx * l sum (k / l) * l){ans l;break;}if(l - (sum % l) k mx * l (sum l - (sum % l)) ((k - (l - (sum % l))) / l) * l){ans l;break;}}cout ans \n;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t1;cin t;while(t--){solve();}return 0;
}
