UVa11729——算法竞赛入门经典训练指南

浏览数：38 / 时间：2015年06月08日

(xl)LT1-2

这道题还是没什么难度，但是注意一下运算符重载，以便sort，以及构造成员，还有sort遇到vector用迭代器。

写了两份代码。

先附上自己的普通方法：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn=1000+5;

struct soldier{
    int b;
    int j;
    bool operator <(const soldier &a)const{
        return j>a.j;
    }
}; 
soldier A[maxn];

int main()
{
    int n,kase=0;
    while(scanf("%d",&n)==1&&n){
        for(int i=0;i<n;i++)scanf("%d %d",&A[i].b,&A[i].j);
        sort(A,A+n);
        int ans=0;
        int tot=0;
        for(int i=0;i<n;i++){
            tot+=A[i].b;
            if(tot+A[i].j>ans)ans=tot+A[i].j;
        }
        kase++;
        cout<<"Case "<<kase<<": "; 
        cout<<ans<<endl;
    }
    return 0;
}

再附上高大上的vector等方法，来源于原书的方法：

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Job{
    int j,b;
    bool operator <(const Job& x) const {        //运算符重载格式，不要忘记const 修饰符 
        return j>x.j;
    }
};

int main()
{
    int n,b,j,kase=1;
    while(scanf("%d",&n)==1&&n){
        vector<Job>v;                            //使用不定长数组 
        for(int i=0;i<n;i++){
            scanf("%d%d",&b,&j);
            v.push_back((Job){j,b});            //push_back （Job）{} 
        }
        sort(v.begin(),v.end());                //迭代器 
        int s=0;
        int ans=0;
        for(int i=0;i<n;i++){
            s+=v[i].b;
            ans=max(ans,s+v[i].j);
        }
        printf("Case %d: %d\n",kase++,ans);
    }
    return 0;
}