竹園論壇

標題: b231 - TOI2009 第三題：書 [打印本頁]

作者: Sylveon 時間: 2014-6-28 21:57
標題: b231 - TOI2009 第三題：書
原題：http://zerojudge.tw/ShowProblem?problemid=b231
解題方向：貪心

基本的排程問題，舉幾個例子，排序一下就能找出理想順序了

/**********************************************************************************/
/*  Problem: b231 "TOI2009 第三題：書" from 2009 TOI 研習營初選       */
/*  Language: CPP (458 Bytes)                                                    */
/*  Result: AC(4ms, 260KB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2013-02-22 22:19:25                                     */
/**********************************************************************************/

#include<cstdio>
#include<algorithm>
using namespace std;
struct _data{
int A,B;
}data[1001];

bool operator<(const _data &a,const _data &b)
{
return a.B>b.B;
}

int main()
{
int N;
int ta,tb;
while(~scanf("%d",&N))
{
for(int a=0;a<N;a++)scanf("%d%d",&data[a].A,&data[a].B);
sort(data,data+N);
ta=tb=0;
for(int a=0;a<N;a++)
{
ta+=data[a].A;
tb=max(tb,ta+data[a].B);
}
printf("%d\n",tb);
}
return 0;
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)