题目解析
给定n所学校，以及每间考场的容量。
问每个学校需要几个考场，以及总考场数
解题思路
模拟
可以使用优先队列来实现
每次将最少的剩余排队人数 拿来去判断 三种情况
- 如果人数大于等于每间考场容量：新开一间考场，当前考场剩余容量为0。再将剩余的人数再次去排队
- 如果当前人数小于容量且能在已有的考场中找到能容纳的考场，则将这些人放入该考场
- 否则，新开一间考场，剩余人数 = 每间考场容量 - 人数
注: 不知道为啥java的最后一个数据就是答案错误
代码
import java.io.*;
import java.util.*;
public class Main
{
static int N = (int) 1e4 + 10;
static int M = (int) 1e4;
static String school[] = new String[N + 10]; // 学校名称
static int cnt[] = new int[N + 10]; // 每个学校需要的考场
static int pos[] = new int[N * 500 + 10]; // 每个考场剩余的人数
static PriorityQueue<Integer> pr = new PriorityQueue<Integer>(); // 剩余排队的人数，以及编号 （人数 * 10000 + 编号）
public static void main(String[] args)
{
int n = sc.nextInt();
int c = sc.nextInt();
for (int i = 1; i <= n; i++)
{
school[i] = sc.next();
int num = sc.nextInt();
pr.offer(num * M + i);
}
int res = 0; // 考场数量
while (pr.size() > 0)
{
int u = pr.poll();
int k = u / M; // 学校剩余人数
int id = u % M; // 学校编号
cnt[id]++; // 当前学校考场增加一个
// 是否有满足条件1的考场
if (k >= c)
{
pos[++res] = 0; // 新增考场，剩余人数为0
k -= c; // 学校剩余人数
if (k != 0)
pr.add(k * M + id); // 当前学校处理下一轮
continue;
}
// 是否有满足条件2的考场
boolean f = false;
for (int i = 1; i <= res; i++)
{
if (pos[i] >= k)
{
f = true;
pos[i] -= k; // 更新当前考场剩余的人数
break;
}
}
// 是否有满足条件3的考场
if (!f)
pos[++res] = c - k; // 新开一个考场
}
for (int i = 1; i <= n; i++)
out.println(school[i] + " " + cnt[i]);
out.println(res);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}
c++
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e4 + 10, M = 1e4;
string school[N]; // 学校名称
int cnt[N]; // 每个学校需要的考场
int pos[N * 500]; // 每个考场剩余的人数
priority_queue<int> q; // 剩余排队的人数，以及编号 （人数 * 10000 + 编号）
int main()
{
int n, c; cin >> n >> c;
for(int i = 1; i <= n; i ++)
{
int x; cin >> school[i] >> x;
q.push(x * M + i);
}
int res = 0; // 考场数量
while(q.size() > 0)
{
int u = q.top(); q.pop();
int k = u / M; // 学校剩余人数
int id = u % M; // 学校编号
cnt[id] ++; // 当前学校考场增加一个
// 是否有满足条件1的考场
if(k >= c)
{
pos[++res] = 0; // 新增考场，剩余人数为0
k -= c; // 学校剩余人数
if(k > 0) q.push(k * M + id); // 当前学校处理下一轮
continue;
}
// 是否有满足条件2的考场
bool f = false;
for(int i = 1; i <= res; i ++)
{
if(pos[i] >= k)
{
f = true;
pos[i] -= k; // 更新当前考场剩余的人数
break;
}
}
// 是否有满足条件3的考场
if(!f) pos[++res] = c - k; // 新开一个考场
}
for(int i = 1; i <= n; i ++)
cout << school[i] << " " << cnt[i] << endl;
cout << res;
return 0;
}