上海计算机学会2024年11月月赛C++乙组T1放置小球
发布时间
阅读量：
阅读量
放置小球
内存限制: 512 Mb时间限制: 1000 ms
题目描述
共有m种不同颜色的小球；Alice拥有第i种颜色的小球ai个以及n个空盒子。
每当每个球都被放置到一个盒子里，并且每个盒子里的所有球都是不同颜色的时
在任意的合法放置方案中，最少需要多少个盒子容纳m个小球？希望确定该最小值。
保证至少有一个有效的放置方案（ai≤n）。
输入格式
第一行一个整数 T 代表数据组数，对于每组数据：
第一行两个整数 n,m 表示颜色数和球数。
第二行 m 个整数 a1,a2,⋯,am 表示每种颜色的球数。
输出格式
对于每组数据，一行一个整数表示答案。
数据范围
对于 30% 的数据，T=1，n≤5，m≤5。
对于 60% 的数据，T=1，n,m≤1000。
对于 100% 的数据，1≤T≤10，1≤n,m≤10^5，1≤ai≤n。
样例数据
将n=1,5,3分别放入相应的行中，并在输出部分说明具体的放置方式：使用三个盒子分别放置三种不同颜色的小球；第四个盒子里放入编号为1和2的小球各一颗；第五个盒子里放入编号为1和3的小球各一颗。
解析如下：将i号小球放入n个盒子中，则必定会有(n−a_i)个盒子中没有i号小球。为了尽可能减少含有m个小球的盒子数量，则应通过合理安排各编号小球的位置来避免重叠存放，并需注意其中最小值为0
详见代码：
#include<bits/stdc++.h>
using namespace std;
int t, m, n, a;
int main() {
cin >> t;
while(t--) {
cin >> n >> m;
int ans = n;//初始化为n
for(int i = 1; i <= m; i++) {
cin >> a;
ans -= n - a;//每次去掉缺少i号小球的盒子
}
cout << max(ans, 0) << endl;//答案最小为0
}
return 0;
}
AI写代码全部评论 (0)
还没有任何评论哟~