「NOIP2011」观光公交
2024-09-03 19:38:33
传送门
Luogu
解题思路
有点麻烦,幸好 \(O(n^2)\) 能过。。。
贪心地想一想,我们如果要用加速器,肯定是要选择车上人数最多的时段加速。
但是我们就会面临这样的情况:
- 加速了,带来了增益(人等车的时间或者人到站的时间减少)
- 加速了,但是没有增益(也就是车子还是要等人)
那么我们就分类讨论一下,预处理一些东西:
每个站的下车人数,需要更新的车到站时间,每个站的最后一个下车人数。
然后随便搞一下就好了。
细节注意事项
- 细节有点多
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 1010;
const int __ = 10010;
int n, m, k, d[_];
int off[_], arr[_], las[_];
int t[__], a[__], b[__];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), read(k);
for (rg int i = 1; i <= n - 1; ++i) read(d[i]);
for (rg int i = 1; i <= m; ++i) {
read(t[i]), read(a[i]), read(b[i]);
++off[b[i]], las[a[i]] = max(las[a[i]], t[i]);
}
arr[1] = 0;
for (rg int i = 2; i <= n; ++i)
arr[i] = max(arr[i - 1], las[i - 1]) + d[i - 1];
while (k--) {
int tmp = 0, pos;
for (rg int i = 2; i <= n; ++i) {
if (!d[i - 1]) continue;
int _tmp = 0;
for (rg int j = i; j <= n; ++j) {
_tmp += off[j]; if (arr[j] <= las[j]) break;
}
if (tmp < _tmp)
tmp = _tmp, pos = i;
}
--d[pos - 1];
for (rg int i = pos; i <= n; ++i) {
--arr[i]; if (arr[i] < las[i]) break;
}
}
int ans = 0;
for (rg int i = 1; i <= m; ++i)
ans += arr[b[i]] - t[i];
printf("%d\n", ans);
return 0;
}
完结撒花 \(qwq\)
最新文章
- C#4.0泛型的协变,逆变深入剖析
- bzoj3052: [wc2013]糖果公园
- [.net core]简介(转)
- python的基础知识
- Java并发编程笔记—基础知识—实用案例
- jquery博客收集的IE6中CSS常见BUG全集及解决方案
- 如何监控 Tomcat?Zabbix 与 Cloud Insight 对比
- 在js脚本里计算多个小数的加法问题
- js正则表达式中的问号使用技巧总结
- git创建与合并分支
- leetcode_question_115 Distinct Subsequences
- VC 为静态控件添加事件
- CSS定位与层叠
- boost库之shared_ptr
- 触发器 评论折叠显示(jquery)
- Android Activity生命周期图解
- 20175212童皓桢 《Java程序设计》第一周学习
- C#实现多态之接口。
- 常见 User-Agent 大全(自己在用)
- pip 安装指定版本软件包