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 523064456 at 2015-04-01 21:36:43 on Problem 3045
这题目贪心的思路大家都想得到,但很多人都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:
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