首页 > ACM题库 > HDU-杭电 > hdu 3090 Go Home-贪心[解题报告]C++
2014
03-01

hdu 3090 Go Home-贪心[解题报告]C++

Go Home

问题描述 :

There comes the holiday, Partychen set foot on the way home. He takes some ECNU coins to hire bodyguards to prevent from being robbed before he went home. But the bodyguard takes one coin for every kilometer. If Partychen walks without bodyguard , he will be robbed one ECNU coin by every robber on every kilometer . Of course , he can choose where to hire bodyguard or where to be robbed as he like.
For example , there are two roads on his way home and he wants to use 8 ECNU coins to hire bodyguard , the first road takes 4 kilometers with 5 robbers ( per kilometer ) and the second takes 5 kilometers with 6 robbers. He could choose the last 3 kilometers on the first road and the whole kilometers on the second road to hire bodyguard to protect him, and leave the first kilometer on the first road to be robbed by 5 robbers, which he will be robbed 5 ECNU coins.
Now , Partychen want to know how many ECNU coins will be robbed at least.

输入:

It consists of multi-case .
Every case starts with two integers N and M ( 0�N�10,000, 0�M�1,000,000,000 ) which means that there are N roads and M ECNU coins to hire bodyguard.
The followed N lines contains two integers D and P (1<=D<=10,000 , 0<=P<=10 ) , which means the length of every road and the number of robbers in every kilometer on this road.
End with N=0 and M=0 .

输出:

It consists of multi-case .
Every case starts with two integers N and M ( 0�N�10,000, 0�M�1,000,000,000 ) which means that there are N roads and M ECNU coins to hire bodyguard.
The followed N lines contains two integers D and P (1<=D<=10,000 , 0<=P<=10 ) , which means the length of every road and the number of robbers in every kilometer on this road.
End with N=0 and M=0 .

样例输入:

2 8
4 5
5 6 
3 1
5 10
5 10
5 10
0 0

样例输出:

5 
140

没有什么难度。贪心,按强盗个数排序就行了。水题,终于排了个第一

Rank Author Exe. Time Exe. Memory Code Len. Language Date
1 从此醉 46MS 340K 696B C++ 2014-03-04 14:48:58
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Node{
	int d,p;
};
Node roads[10001];
int n,m;
int sum;
bool cmp(const Node & n1,const Node & n2){
	return n1.p > n2.p;
}
int main(){
	while(scanf("%d %d", &n, &m), m!=0 || n!=0){
		sum = 0;
		for(int i=0; i<n; i++){
			scanf("%d%d", &roads[i].d, &roads[i].p);
			sum += roads[i].d*roads[i].p;
		}
		sort(roads, roads+n, cmp);
		for(int i=0; i<n; i++){
			if(m > roads[i].d){
				m -= roads[i].d;
				sum -= roads[i].d * roads[i].p;
		    }else{
		    	sum -= m * roads[i].p;
		    	break;
		    }
		}
		printf("%d\n",sum);
	}
	return 0;
}

ACM之家原创


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks