| ||||||||||
| 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