当前位置:编程学习 > C/C++ >>

HDU 4296 Buildings(贪心)

[cpp] 
/*
贪心:s2 - w1 > s1 - w2
*/ 
#include <cstdio> 
#include <cstdlib> 
const int nMax = 100007; 
struct Node 

    int wi, si; 
}node[nMax]; 
int N; 
 
int cmp(const void *a, const void *b) 

    Node *pa = (Node *) a; 
    Node *pb = (Node *) b; 
    return (pa->si - pb->wi) - (pb->si - pa->wi); 

 
int main() 

    while(scanf("%d", &N) != EOF) 
    { 
        int i; 
        for(i = 0; i < N; ++ i) scanf("%d%d", &node[i].wi, &node[i].si); 
        qsort(node, N, sizeof(node[0]), cmp); 
        __int64 sum = node[0].wi, ans = 0; 
        for(i = 1; i < N; ++ i) 
        { 
            __int64 tmp = sum - node[i].si; 
            if(tmp > ans) ans = tmp; 
            sum += node[i].wi; 
        } 
        printf("%I64d\n", ans); 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,