数学技巧巧夺最优解！

· · 题解

题目大意

有 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”这个新东西~