最优排名

Posted on Edited on In

题目大意：\(A\)君和\(B\)君准备参加\(C\)国举办的\(WGP\)。比赛规则为若赢得一场游戏的胜利则会获得一点马力值，但每个队伍有一个马力值上限\(w_i\)，若超过上限则会变为\(0\)。马力从高到低进行排名，马力一样则视为排名一样。比赛已经结束，参赛队伍通过比赛获得的马力为\(v_i\)。\(A\)君是一个马力爆棚的人因此他喜欢把自己多余的马力给别人来奶死对面。现在\(B\)君想知道\(A\)君在将马力合理卖完马之后自己队伍的最高排名是多少。（来自Ame__的题目翻译）

贪心就完事了，做法实现很多，这里介绍一种

排个序，然后拎出原来那个，每次把比他大的里边\(w_i-v_i\)最小的那个干掉，然后自己往后战略性撤退，把比自己大的再押进去

考试时候傻逼了，写完之后看到数据范围，嫌麻烦，没开ll，准备最后再开

然后最后的时候忘了，挂掉五十分

注意一个小细节：能减就一直减，当我们要减为0的时候，一定不会使得答案变得更差（想一想，为什么？）

讨论两种情况，当前答案后面有数字，和后面没有数字

  • 后面没有数字，也就是干掉他之后，大家都是0，而题目告诉我们，马力一样的排名一样，我前边的人少了一个，我的排名一定会更优
  • 后面有数字，我变成0一定不能再减少了，所以我不干掉他一定是最优的，咦，这个答案不是在上次就已经取到了吗？所以即使这次不优，对上次的ans没有丝毫影响

代码如下（外加一组调试数据和痕迹）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 66;

struct yhzhyhm
{
    int v, w, id;
    bool operator < (const yhzhyhm &x) const
    {
        return (v > x.v) || ((v == x.v) && (id < x.id));
    }
}yh[N];

priority_queue<int, vector<int>, greater<int> >q;

signed main()
{
    int i, x, n = read();
    for (i = 1; i <= n; ++ i) yh[i].v = read(), yh[i].w = read(), yh[i].id = i;
    x = yh[1].v;
    sort(yh + 1, yh + 1 + n);
cout << "------------------------\n";
for (i = 1; i <= n; ++ i) cout << yh[i].v << ' ' << yh[i].w << '\n';
    for (i = 1; i <= n; ++ i)
    {
        if (yh[i].id == 1) break;
        q.push(yh[i].w - yh[i].v + 1);
    }

    int res = i, rnk = i, pos = i, ret = x, pd = 1;
/*
res is answer
rnk is now_pai_ming
pos is now_wei_zhi
ret is now_shengyu
pd is now_tag
*/
cout << "rnk--->" << rnk << '\n';
    while (! q.empty() && pd == 1)
    {
        pd = 0, x = q.top(); q.pop();
cout << "x-->" << x << '\n';
        if (ret >= x) ret -= x, pd = 1;
        if (! pd) break;
        int num = 0;
        for (i = pos + 1; i <= n; ++ i)
        {
            if (yh[i].v <= ret) break;
            ++ num;
            q.push(yh[i].w - yh[i].v + 1);
        }
        pos = i - 1, rnk = rnk - 1 + num;

cout << "now_rnk->" << rnk << '\n';
cout << "now_pos--->" << pos << '\n';

        res = min(res, rnk);
    }
    
    put(res);
    return 0;
}
/*
10
25 38
45 48
9 13
49 50
12 14
41 42
34 37
46 49
14 15
23 26
*/