Commando War (贪心)

时间:2021-04-29 03:56:48

Waiting for orders we held in the wood, word from the front never came

By evening the sound of the gunfire was miles away

Ah softly we moved through the shadows, slip away through the trees

Crossing their lines in the mists in the fields on our hands and our knees

And all that I ever, was able to see

The fire in the air, glowing red, silhouetting the smoke on the breeze

There is a war and it doesn't look very promising for your country. Now it's time to act. You have a commando squad at your disposal and planning an ambush on an important enemy camp located nearby. You have N soldiers in your squad. In your master-plan, every single soldier has a unique responsibility and you don't want any of your soldier to know the plan for other soldiers so that everyone can focus on his task only. In order to enforce this, you brief every individual soldier about his tasks separately and just before sending him to the battlefield. You know that every single soldier needs a certain amount of time to execute his job. You also know very clearly how much time you need to brief every single soldier. Being anxious to finish the total operation as soon as possible, you need to find an order of briefing your soldiers that will minimize the time necessary for all the soldiers to complete their tasks. You may assume that, no soldier has a plan that depends on the tasks of his fellows. In other words, once a soldier begins a task, he can finish it without the necessity of pausing in between.

Input

There will be multiple test cases in the input file. Every test case starts with an integer N (1<=N<=1000), denoting the number of soldiers. Each of the following N lines describe a soldier with two integers B (1<=B<=10000) & J (1<=J<=10000). B seconds are needed to brief the soldier while completing his job needs J seconds. The end of input will be denoted by a case with N =0 . This case should not be processed.

Output

For each test case, print a line in the format, Case X: Y, where X is the case number & Y is the total number of seconds counted from the start of your first briefing till the completion of all jobs.

Sample Input Output for Sample Input

3

2 5

3 2

2 1

3

3 3

4 4

5 5

0

Case 1: 8

Case 2: 15

题解:贪心,按执行任务的时间从大到小排,得到的就是最优解

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; struct node
{
int b,j;
}p[1005]; bool cmp(node x,node y)
{
return x.j>y.j;
}
int main()
{
int N;
int cnt=1;
while(scanf("%d",&N)&&N)
{
for(int t=0;t<N;t++)
{
scanf("%d%d",&p[t].b,&p[t].j);
}
sort(p,p+N,cmp);
long long int s=0,sum=0;
for(int t=0;t<N;t++)
{
s+=p[t].b;
sum=max(sum,s+p[t].j);
}
printf("Case %d: %lld\n",cnt++,sum);
}
}

Commando War (贪心)的更多相关文章

  1. UVa 11729 - Commando War&lpar;贪心&rpar;

    "Waiting for orders we held in the wood, word from the front never came By evening the sound of ...

  2. UVA 11729 - Commando War(贪心 相邻交换法)

    Commando War There is a war and it doesn't look very promising for your country. Now it's time to ac ...

  3. Uva 11729 Commando War (简单贪心)

    Uva 11729  Commando War (简单贪心) There is a war and it doesn't look very promising for your country. N ...

  4. 贪心 UVA 11729 Commando War

    题目传送门 /* 贪心:按照执行时间长的优先来排序 */ #include <cstdio> #include <algorithm> #include <iostrea ...

  5. uva----11729 Commando war &lpar;突击战争&rpar;

    G Commando War Input: Standard Input Output: Standard Output “Waiting for orders we held in the wood ...

  6. cogs 1446&period; &lbrack;Commando War&comma;Uva 11729&rsqb;突击战

    1446. [Commando War,Uva 11729]突击战 ★   输入文件:commando.in   输出文件:commando.out   简单对比时间限制:1 s   内存限制:64 ...

  7. Commando War

    Commando War“Waiting for orders we held in the wood, word from the front never cameBy evening the so ...

  8. &lbrack;ACM&lowbar;水题&rsqb; UVA 11729 Commando War &lbrack;不可同时交代任务 可同时执行 最短完成全部时间 贪心&rsqb;

    There is a war and it doesn't look very promising for your country. Now it's time to act. You have a ...

  9. 【贪心】【Uva11729】 Commando War

    你有n个部下,每个部下需要完成一项任务.第i个部下需要你花Bi分钟交待任务,然后他会立刻独立地.无间断地执行Ji分钟后完成任务.你需要选择交待任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任 ...

随机推荐

  1. Redis&lowbar;高可用方案Sentinel配置

    最小化的sentinel配置文件为: 1 port 7031 2 3 dir /opt/app/redis/redis-2.8.17/tmp 4 5 sentinel monitor mymaster ...

  2. PHP中的赋值运算符

    PHP的赋值运算符有两种,分别是: (1)“=”:把右边表达式的值赋给左边的运算数.它将右边表达式值复制一份,交给左边的运算数.换而言之,首先给左边的运算数申请了一块内存,然后把复制的值放到这个内存中 ...

  3. c&num;中struct和class的区别 详细&lbrack;转&rsqb;

    转自:http://blog.csdn.net/justlovepro/archive/2007/11/02/1863734.aspx 有这么几点不同: 1.struct 是值类型,class是对象类 ...

  4. asp自动解析网页中的图片地址,并将其保存到本地服务器

    程序实现功能:自动将远程页面的文件中的图片下载到本地. 程序代码 <% '将本文保存为 save2local.asp '测试:save2local.asp?url=http://ent.sina ...

  5. iOS NSDatePicker

    1.NSDate类 1>NSDate是系统一个日期,时间类 2>就是返回当前的日期,时间 3>+(id)date; 4>返回未来secs秒后的日期,时间 5>+(id)d ...

  6. Webfrom 生成流水号 组合查询 Repeater中单选与复选控件的使用 JS实战应用

                                             Default.aspx 网页界面 <%@ Page Language="C#" AutoE ...

  7. raid卡MegaCli工具使用说明

    一.DELL&IBMMegaCli -AdpAllInfo -aALL —看配置项 #检查raid级别MegaCli -LDInfo -Lall -aALL | grep 'RAID Leve ...

  8. web driver下载地址(selenium-3&period;141&lowbar;浏览器版本对应)

    web driver: (Windows环境下) Firefox(上一目录可以找其他浏览器的driver) : 1)http://npm.taobao.org/mirrors/geckodriver/ ...

  9. spring mvc 返回类型

    spring mvc处理方法支持如下的返回方式:ModelAndView, Model, ModelMap, Map,View, String, void 小结:1.使用 String 作为请求处理方 ...

  10. MongoDB树形结构表示法

    http://docs.mongodb.org/manual/tutorial/model-tree-structures/ MongoDB五种树形结构表示法 第一种:父链接结构 db.categor ...