和这道题真的有壁,拿起来就做,然后做错了。又看了半天题目,才知道大概啥意思。
每一轮都需要给人数最多的学校分配位置,如果人数大于c,分配一个教室剩下的人还要再放回进行第二轮,而不是一次性给这个学校分配完。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
string sname[maxn];
int renshu[maxn], pos[maxn],cnt[100*maxn];//cnt人数,pos第i个学校需要的考场数量,第i个考场剩余的人数
priority_queue<pair<int, int>> pq;//人数-学校编号
map<int, int> rest;
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> sname[i] >> renshu[i];
pq.push({ renshu[i],i });
}
int kccnt = 0;
while (!pq.empty()) {
int k = pq.top().first;
int sno = pq.top().second;
pq.pop();
pos[sno]++;//涉及一个考场
if (k >= c) {
cnt[++kccnt] = 0;
k -= c;
if (k) {
pq.push({k,sno});
}
continue;
}
int flag = 0;//是否找到了满足需求的考场
for (int i = 1; i <= kccnt; i++) {
if (cnt[i] >= k) {
flag = 1;
cnt[i] -= k;
break;
}
}
if (!flag) cnt[++kccnt] = c - k;
}
for (int i = 1; i <= n; i++) {
cout << sname[i] << " " << pos[i] << '\n';
}
cout << kccnt << '\n';
return 0;
}
标签:cnt,pq,int,renshu,考场,L2,天梯,046,maxn
From: https://www.cnblogs.com/chengyiyuki/p/18102506