专栏文章
题解：P14613 [2019 KAIST RUN Fall] And the Winner Is... Ourselves!
P14613题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mimzgdf3
- 此快照首次捕获于
- 2025/12/01 18:04 3 个月前
- 此快照最后确认于
- 2025/12/01 18:04 3 个月前
P14613 题解
题目思路
根据题意我们可以发现，罚时只参与最终总时间的计算，而不参与实际比赛时间的计算。所以我们可以先把罚时的部分摘出来计算，然后再考虑剩下的纯解题时间。
这样的话就变成了一个典型的“接水问题”，结论是按照解题时间从小到大排序后计算，证明仿照贪心的证明方法，具体证明过程在下一段。
假设当前有两道题，解题时间分别为 和 ，其中钦定 （ 的情况交换与否都可以，这里不讨论）。当先解决第一题时，第一题耗费时间 ，第二题耗费时间 ，总时间 ；当先解决第二题时，第二题耗费时间 ，第一题耗费时间 ，总时间 。又因为 ，所以先解决第一题时间更小，即按照 顺序解题更优，也就是从小到大排序。
题目代码
CPP#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;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...