2020 ICPC济南 D

Fight against involution

题目大意:

n个人,每人论文字数(w_i)在区间([L_i, R_i])上,每人成绩为(n-K_i)(K_i)为字数大于自己的人数,要求在每人成绩不低于自己最优情况能得到的成绩下尽量减少(sum_{i=1}^{n} w_i)

思路:

注意对题目中(K_i)的理解

The grade of the i-th student (g_i) is (n-K_i)(K_i) is the number of (j in [1, n]) satisfies that (w_j > w_i).

"the number of……satisfies that……"应译为满足……情况的数量。

我们可以“模拟”减轻内卷的这个过程。

假定所有人都在卷,每人论文字数就都为(R_i),我们以(R_i)为第一关键词从小到大排序,就可以得到每个人最优情况下能得到的成绩。

此时要减轻内卷,同时不低于能拿到的最优成绩,则以(L_i)为第二关键词从大到小排序,即可保证原来的排名,同时尽量减小(w_i)

[L1---------R1]
     [L2----R2]

(R1==R2)时,为了不改变原来的排名,需要(L1==L2)

Code:
n = int(input())
stu = []
for i in range(n):
    a, b = map(int, input().split())
    stu.append((a, b))
stu.sort(key=lambda x: (x[1], -x[0]))
last = 0
ans = 0
for i in range(n):
    last = max(last, stu[i][0])
    ans += last
print(ans)
原文地址:https://www.cnblogs.com/Nepenthe8/p/14315531.html