2250.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2250 on 2006-05-22 at 20:50:00 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int YEAR = 12*31;
const int TN = 102400;

class Trip {
public:
	int time, cost, prev;
	double VIPc;
	void make();
	bool operator <(const Trip& t) const { return time < t.time; }
};
void Trip::make() {
	int y, m, d;
	scanf("%d-%d-%d %d", &y, &m, &d, &cost);
	time = y*12*31+m*31+d;
}

Trip t[TN];

int main()
{
	int n, i;
	double cost[TN];
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) t[i].make();
		sort(t, t+n);
		int b = 0, e, tc = 0;
		for(e = 0; e < n; e++) {
			tc += t[e].cost;
			while(t[e].time-t[b].time >= YEAR) tc -= t[b++].cost;
			t[e].prev = b; t[e].VIPc = tc / 2.0;
		}
		cost[0] = 0;
		for(i = 0; i < n; i++)
			cost[i+1] = min(cost[i]+t[i].cost, cost[t[i].prev]+t[i].VIPc+500);
		printf("%.1lf\n", cost[n]);
	}
	
	return 0;
}