题解：P14613 [2019 KAIST RUN Fall] And the Winner Is... Ourselves!

· · 题解

P14613 题解

题目思路

根据题意我们可以发现，罚时只参与最终总时间的计算，而不参与实际比赛时间的计算。所以我们可以先把罚时的部分摘出来计算，然后再考虑剩下的纯解题时间。

这样的话就变成了一个典型的“接水问题”，结论是按照解题时间从小到大排序后计算，证明仿照贪心的证明方法，具体证明过程在下一段。

假设当前有两道题，解题时间分别为 a 和 b，其中钦定 a < b（a = b 的情况交换与否都可以，这里不讨论）。当先解决第一题时，第一题耗费时间 a，第二题耗费时间 a + b，总时间 2a + b；当先解决第二题时，第二题耗费时间 b，第一题耗费时间 a + b，总时间 a + 2b。又因为 a < b，所以先解决第一题时间更小，即按照 a < b 顺序解题更优，也就是从小到大排序。

题目代码

#include<bits/stdc++.h>
using namespace std;
int cost[12];
int ans = 0;
signed main()
{
    for(int i = 1 ; i <= 11 ; i++)
    {
        cin >> cost[i];
        int V;
        cin >> V;
        ans += V * 20;
    }
    sort(cost + 1 , cost + 12);
    for(int i = 1 ; i <= 11 ; i++)
    {
        cost[i] += cost[i - 1];
        ans += cost[i];
    }
    cout << ans << endl;
    return 0;
}