题意
n个软件,每个软件都有种类,而屏幕有容量 s (自己决定),
有两个限制:
- 一个屏幕只能放 s-1 或者 s 个软件
- 一个屏幕上只能防同种的软件
求最小的屏幕数。
思路
枚举 s
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e6+10;
int a[N];
map<int,int> mp;
set<int> st;
int n;
int check(int x){
int ans=0;
for(int it:st){
if(mp[it]%x==0)
ans+=mp[it]/x;
else if(mp[it]/x+mp[it]%x>=x-1)//放满的每页少放一个 + 不足一页剩下的,如果能凑成1页就行
ans+=mp[it]/x+1;
else
return 0x3f3f3f3f;
}
return ans;
}
void solve(){
mp.clear();
st.clear();
scanf("%d",&n);//n个app
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
mp[a[i]]++;
st.insert(a[i]);
}
int minn=0x3f3f3f3f;
for(int it: st)
minn=min(mp[it],minn);
int ans=0x3f3f3f3f;
for(int i=1;i<=minn+1;i++){
ans=min(ans,check(i));
}
printf("%d\n",ans);
}
int main()
{
int t;cin>>t;
while(t--){
solve();
}
return 0;
}
标签:return,Just,Icons,int,CodeForces,st,mp,ans,屏幕
From: https://www.cnblogs.com/kingwz/p/16850308.html