Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
前面很多贴说只比较上一周的,这里贴一个比较之前周的优先队列实现这题数据确实水,只需要比较上一周,但是刷题嘛,还是考虑全面比较好,优先队列实现的AC代码如下 #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<vector> #include<queue> #include<cmath> #include<cstdio> #include<set> #include<bitset> #include<stack> #define MAX_WEEK 10010 using namespace std; int N, S; long long allcost=0; struct node { int cost, submit, produce; friend bool operator<(node a, node b) {return a.cost > b.cost;} }cows[MAX_WEEK]; int main() { scanf("%d%d", &N, &S); for(int i=0; i<N; i++) scanf("%d%d", &cows[i].cost, &cows[i].submit); priority_queue<node> que; allcost += cows[0].submit * cows[0].cost; cows[0].cost += S; que.push(cows[0]); for(int i=1; i<N; i++) { node temp = que.top(); que.pop(); if(cows[i].cost > temp.cost) allcost += 1ll * temp.cost * cows[i].submit; else allcost += 1ll * cows[i].cost * cows[i].submit; cows[i].cost += S; temp.cost += S; que.push(cows[i]); que.push(temp); } cout << allcost << endl;; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator