珠海做网站公司哪家好/b站推广引流最佳方法

C. Phoenix and Towers

题意：给n个大于等于1且小于等于x的高度值，将它们分配给m个位置，每个位置的高度为分配的数值之和，要使得m个位置两两之间高度差不超过x。

思路：假设这m个位置都合法填入，如果再插入一个不大于x的数，加到最小的数上边有两种情况：一：最小的数 + 新插入的数大于最大值，倒数第二小的数变成了最小的数，因为新插入的数小于等于x，所以新的最大的数减去当前最小的数(也就是原来第二小的数一定大于等于x)；二、最小的数 + 新插入的数小于等于最大值，那么序列的最大差值可能会减小，绝对不会增大，所以答案一直都是YES，使用小根堆存储当前值即可

具体代码如下

#include<bits/stdc++.h>using namespace std;const int N = 100010;int n, m, x;struct Node
{int h, id;bool operator < (const Node &H) const{return h > H.h;}
};int main()
{int T;scanf("%d", &T);while(T --){scanf("%d%d%d", &n, &m, &x);puts("YES");priority_queue<Node> heap;for(int i = 1; i <= m; ++ i) heap.push({0, i});for(int i = 1; i <= n; ++ i){int v;scanf("%d", &v);auto temp = heap.top();heap.pop();printf("%d ", temp.id);heap.push({temp.h + v, temp.id});}}return 0;
}