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