CodeForces - 985C Liebig‘s Barrels

题目链接

https://codeforces.com/problemset/problem/985/C

解题思路

完整叙述我的思考过程（1h10min AC 我是fw）

（题目中的l，我用d表示）

如果题目要求最小值，大家应该都会。从小到大排序，选择最小的n个作为每个桶的短板，所以最小值为最小的n个板长之和； 但是题目要求最大值，如果还按求最小值的贪心思路来求显然不对，例如，板子为1 1 2 2 2 2 3 3，桶数n为4，每个桶的板子数k为2，若按最小值贪心，分配方式为1 2、1 2、2 3、2 3，和为1+1+2+2 = 6，但是按照1 1、2 2、2 3、2 3的方式分配，和为7，所以最小值的贪心方式不好用了。

min(a[i])表示板子中最短长度，min(a[i]) ~ min(a[i]) + d长度范围内的板子的分配会影响最终的和，至于有的桶被分配到的板子数不到k，完全可以用长度长于min(a[i]) + d的板子去填补，并不会影响和的最大值，因为全部板子中最短的长度是确定的，因此能作为某个桶的短板的板子的长度不得大于min(a[i]) + d，所以这些用于填补的板子的长度永远不能当作任何桶短板，否则必不满足“任意两个桶的短板之差不超过d”的条件。 这样一来问题就转换成了如何分配这些长度在min(a[i]) ~ min(a[i]) + d范围内的板子了。

！核心部分！ 从大方面考虑，无非就是先为每个桶分配短板子还是长板子： 1、假如，先分配短板子。 为保证和最大，我们需要尽量将短板子分配到一个桶上，就像上面那个例子一样，我们将长度为1的板子分配给同一桶时会得到和的最大值。 但是你怎么知道将多少个短板子分配给当前桶？因为我们要尽量让短板子分到一个桶上，所以自然要将最短的若干个板子分到第一个桶上，这时又会出现两种情况，情况1，最短板子够k个，即能构成第一个桶，此时多余的最短板子必然要分配给第二个桶，这是毫无疑问的，但是情况2，最短的板子不够k个，即无法完全由最短板子构成第一个桶，此时我们要为第一个桶分配若干个次短板子或大于min(a[i]) + d的板子。我们的贪心思路决定了我们必须要连续地分配若干个相同长度的板子给一个桶，要是我们用次短板子去填第一个桶的空缺，就有可能导致后面有的桶的短板可能超出min(a[i]) + d；要是我们用大于min(a[i]) + d的填充，那你会不会想到一种情况，假如在min(a[i]) ~ min(a[i]) + d范围内的板子有1 1 2 3 3，当然还有超范围的我就不列举了，假设存在3个桶吧，第一个桶1 1，第二个桶2，第三个桶3 3，按照上述贪心思路会先这样分配范围内的板子吧，，此时1 1 2、3、3不比上面这个方式更优吗？ 无论如何都无法得到正确的答案。 2、假如，先分配长板子。 这应该是很自然想到的一种方式，先尽可能均分长板子，让尽可能多的桶的短板是长板子，才会让答案更优。 问题就在于如何分配？ 先分长板子，而且尽量让有长板子的桶不要再使用比其短的板子了，要不这长板子岂不白用了？又成了次长板子对答案做贡献了。 那用最长板子（最长板子指的是范围内的最长板子）作为短板的桶的空缺部分咋办？用范围外的板子去填。假设最长板子有t个，若范围外的板子不足以为t个桶剩余的k-1个板子的位置上填满，即范围外的板子不足(k-1) * t个，这样就没法构成t个短板为最长板子的桶了。 那我们就不构成t个呗，我们就看这t个最长板子和范围外的板子总共多少个，设为w个，我们用这w个板子去构成桶不就行了，构成的桶数首先要不大于t个（否则最长板子不够啊），最多能构成w/t个短板为最长板子的桶吧，剩下可能存在未用的板子，无论这些未用的板子是范围外的还是最长板子，现在对于剩下的范围内的板子而言都不会影响构成剩下桶的最短板，因此我们完全可以将这些板子视为范围外的板子。 这样一来范围外的板子就变成上次用范围外的板子与最长板子的总数-构成若干短板为最长板子的桶所用的板子数；而现在又要用次长板子进行填新桶了吧，相当于取代了上一次填桶操作中“最长板子”的位置；以此类推，用次最长板子填完后又可以更新“范围外”的板子个数了。最后得到答案。

注意：LL

代码

#include
using namespace std;
typedef long long LL; // !!!

const int N = 1e5+10;

int n,k,d;
LL a[N], numofi[N]; 
int b[N];
LL ans = 0;

int main()
{
	scanf("%d%d%d", &n, &k ,&d);
	int m = n*k; // 板子总数 
	for(int i = 1;i  d) printf("0\n"); // 没法满足任意两个桶的短板长度差不大于d的条件 
	else {
		// b[i] 表示从小到大第i短的板子的个数 
		int num = 1; // b的元素个数 
		LL up = a[1] + d; // 满足范围的最长板子，即上述最长板子的长度 
		int t = 1; // 保存在范围内的板子个数 
		int upnum = 1; // 最长板子在b数组中对应的下标 
		b[num] = 1;numofi[num] = a[1]; // numofi[i]表示b[i]对应的长度 
		for(int i = 2;i