| ||||||||||
| 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 | |||||||||
给出详解给你们这题目贪心的思路大家都想得到,但很多人都wr很多次不知道为什么,我开始也是这样。看了别人的评论说只有一个的时候,dist是负数,那其实就算不止一个牛,最后总的dis也可能为负数,大家看看w和s的数据范围就可以知道。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node {
int w, s;
bool operator < (const node& x) const {
return x.w + x.s < w + s;
}
};
node cow[50016];
int n;
int main()
{
//freopen("in", "r", stdin);
scanf("%d", &n);
int sum = 0;
for(int i = 0; i < n; ++i) {
scanf("%d %d", &cow[i].w, &cow[i].s);
sum += cow[i].w;
}
sort(cow, cow + n);
int ans = -2000000000;//重点关注ans的初始值
for(int i = 0; i < n; ++i) {
sum -= cow[i].w;
ans = max(ans, sum - cow[i].s);
}
printf("%d\n", ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator