记录编号	326628	评测结果	AAWWWWWWWWWWWWWWWWWW
题目名称	[NOIP 2011]观光公交	最终得分	10
用户昵称	Tabing010102	是否通过	未通过
代码语言	C++	运行时间	0.131 s
提交时间	2016-10-21 11:17:35	内存使用	0.61 MiB

#include <fstream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL maxn = 10000+10;
const LL maxm = 1000+10;
fstream fin, fout;
LL n, m, k;
LL d[maxn];
LL tIme[maxm], from[maxm], to[maxm];
LL spn[maxn];//i->i+1站中间路程的人数(station_passing_num)
LL rt[maxn];//第i站实际走的时间(real_tIme)
LL stwt[maxn];//第i站等待总时间(station_total_wait_tIme)
LL sr[maxn];//间接排序(station_raking)
bool cmp(const int &a, const int &b) {
	if(spn[a] == spn[b]) return stwt[a]<stwt[b];
	else return spn[a]>spn[b];
}
int main() {
	fin.open("bus.in", ios::in);
	fout.open("bus.out", ios::out);
	fin >> n >> m >> k;
	for(LL i = 1; i < n; i++) fin >> d[i];
	for(LL i = 1; i <= m; i++) {
		fin >> tIme[i] >> from[i] >> to[i];
		if(tIme[i] > rt[from[i]]) {
			stwt[from[i]] += spn[i]*(tIme[i]-rt[from[i]]);
			rt[from[i]] = tIme[i];
		} else stwt[from[i]] += rt[from[i]]-tIme[i];
		for(LL j = from[i]; j < to[i]; j++) spn[j]++;
	}
	for(LL i = 1; i <= n; i++)
		rt[i+1] = max(rt[i+1], rt[i]+d[i]);
//	fout << "stwt:";
//	for(LL i = 1; i <= n; i++) fout << stwt[i] << ' ';
//	fout << endl;
	for(LL i = 1; i <= n; i++) sr[i] = i;
	sort(sr+1, sr+1+n, cmp);
	LL p = 1;
	while(k > 0) {//使用加速器
		if(k >= d[sr[p]]) {
			k -= d[sr[p]];
			d[sr[p]] = 0;
			p++;
		} else {
			d[sr[p]] -= k;
			k = 0;
		}
	}
//	fout<< "After speedup, d:";
//	for(LL i = 1; i < n; i++) fout << d[i] << ' ';
//	fout << endl;
	LL ans = 0;
	for(LL i = 1; i <= m; i++) {
		LL nt = tIme[i];
		for(LL j = from[i]; j < to[i]; j++) {
			ans += rt[j]-nt;
//			fout << "rt[j=" << j << "]=" << rt[j] << ' ';
//			fout << "nt=" << nt << ' ';
//			fout << "Value=" << rt[j]-nt << ' ';
//			fout << "ans" << ans << endl;
			nt = rt[j];
			ans += d[j];
			nt += d[j];
		}
	}
	fout << ans;
	return 0;
}