Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

前面很多贴说只比较上一周的,这里贴一个比较之前周的优先队列实现

Posted by maiovo at 2024-08-19 11:33:56 on Problem 2393
这题数据确实水,只需要比较上一周,但是刷题嘛,还是考虑全面比较好,优先队列实现的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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator