自动搬运

查看原文

来自洛谷，原作者为

	CashCollectFactory 这个家伙不懒，但什么都留下了

搬运于2025-08-24 22:19:05，当前版本为作者最后更新于2023-11-20 22:04:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有 $p$ 个人一起去打高尔夫，一共有 $h$ 局，每局每人各有一个杆数。打完之后，他们想把杆数设一个最大值来调整得分，如果某一局杆数超过最大值就把杆数改成这个最大值。问在不同的杆数最大值下，每个人的最高排名分别是多少。

数学解法

对于每个人的总杆数关于杆数限制的函数，是一个分段线性函数，如下图所示。

当限制超过他的最大杆数，直线是平的，前面的线段的斜率就是这个人有多少杆的得分超过了这一个限制。

由此性质，我们不难想出如下做法：

首先，将每个人自己的分数从大到小排序，用两重循环求出每个人的最佳排名，外层循环每次处理一个人，内层循环遍历其他所有人。

对于内层循环，我们首先将两个人的分数从大到小排列，在头部加一个 $+∞$(得分的曲线只会在这些点改变)，作为待选的杆数限制。然后，对每一个限制，调整两人的得分，当且仅当调整前后两人的得分大小关系发生改变，说明两个人的排名发生了变化。

遍历完其他人后，首先可以知道在无限制的情况下的排名，再通过之前整理的排名变化情况，就可以得知在不同限制下的排名，从而得知最佳排名，于是本题就完成啦！

最后，算法的时间复杂度约为 $O(p \times h \times \log ph)$，就此达成本题目目前的最优解！

具体的实现细节见下方代码：

代码时间（码丑勿喷，我颜良文丑）

#include<bits/stdc++.h>
using namespace std;
int main(){
	int P,H;
	while(cin >> P >> H) {
		vector<vector<int>> S(P, vector<int>(H));
		vector<int64_t> tot(P);
		for(int i = 0; i < P; i++) {
			for(int j = 0; j < H; j++) {
				cin >> S[i][j];
				tot[i] += S[i][j];
			}
			S[i].push_back(0); //设置一个最小的地板，在26行的循环递增条件用
			sort(S[i].begin(), S[i].end(), greater<int>());
		}
		for(int i = 0; i < P; i++) {
			vector<pair<int, int>> events; //pair中第一个int为取的lim,第二个表示取此lim时,排名需要如何变化
			int cur = 0;
			for (int j = 0; j < P; j++) {
				int64_t itot = tot[i], jtot = tot[j], lim = 1000000000;
				if (jtot <= itot) cur++;
				for (int ih = 0, jh = 0; ih < H || jh < H; S[i][ih] > S[j][jh] ? ih++ : jh++) {
					bool old = (jtot <= itot); //这里的条件比较巧妙，具体看下面
					int v = max(S[i][ih], S[j][jh]); //不断取ij的scores中较大者为lim,如果有重复,当两个都到达小值时才会进入下一lim
					itot -= (lim-v) * ih; jtot -= (lim-v) * jh; //对两者总score进行裁减
					lim = v;
					if (!old && jtot <= itot) {
						/*排名要+1，在前一lim需要jtot>itot（=不行，因为排名算的是小于等于自己分数的个数），当前lim jtot <= itot
						 *直线过（lim，tot）点，斜率是h，分别列出ij两直线的方程式，求出交点横坐标就是lim+(itot-jtot)/(jh-ih), 同时计算出的是double,需要向下取整(转int已经执行了)
						 *判断条件相当于if(orig_jtot>orig_itot && (jtot<itot || jtot==itot))*/
						events.emplace_back(lim+(itot-jtot)/(jh-ih), 1);
					} else if (old && jtot > itot) {
						/*排名要-1，在前一lim需要jtot<=itot，在当前lim jtot>itot，并且如果交点是整数,-1的效果要计入前一个点，所以会有jtot-itot-1
						 *判断条件相当于if((orig_jtot>orig_itot || orig_jtot==orig_itot) && jtot>itot)*/
						events.emplace_back(lim+(jtot-itot-1)/(ih-jh), -1);
					}
				}
			}
			sort(events.begin(), events.end(), greater<pair<int, int>>());
			int ret = cur;
			for (auto const& e : events) {cur += e.second; ret = min(ret, cur);}
			cout<<ret<<endl;
		}
	}
	return 0;
}

补充一句，本代码需要使用 C++11 以上版本才可以正常编译，只因里面用了“auto”这个新东西~