UVa 11729 Commando War 突击战

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

你有 n 个部下,每个部下需要完成一个任务。第 i 个部下需要你花 Bi 分钟交待任务,然后他会立刻独立地、无间断地执行 Ji 分钟后完成任务。你需要选择交待任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务尽早结束)。注意,不能同时给两个部下交待任务,但部下们可以同时执行他们各自的任务。

既然是要尽早完成任务,当然执行时间长的先交待,先执行。所以对所有数据按执行时间从大到小的顺序进行排序,然后开始处理,通过更新最晚的时间来得到最终结果。

简单的贪心,附上AC代码:

   1: #include <stdio.h>

   2: #include <math.h>

   3: #include <iostream>

   4: #include <cstdarg>

   5: #include <algorithm>

   6: #include <string.h>

   7: #include <stdlib.h>

   8: #include <string>

   9: #include <list>

  10: #include <vector>

  11: #include <map>

  12: #define LL long long

  13: #define M(a) memset(a, 0, sizeof(a))

  14: using namespace std;

  15:  

  16: void Clean(int count, ...)

  17: {

  18:     va_list arg_ptr;

  19:     va_start (arg_ptr, count);

  20:     for (int i = 0; i < count; i++)

  21:         M(va_arg(arg_ptr, int*));

  22:     va_end(arg_ptr);

  23: }

  24:  

  25: typedef struct A

  26: {

  27:     int b, j;

  28:     bool operator < (const A& x) const

  29:     {

  30:         return j > x . j;

  31:     }

  32: }A;

  33:  

  34: int main()

  35: {

  36:     int n, count = 1;

  37:     while (~scanf("%d", &n) && n)

  38:     {

  39:         vector <A> buf;

  40:         int b, j;

  41:         for (int i = 0; i < n; i++)

  42:         {

  43:             scanf("%d%d", &b, &j);

  44:             buf.push_back((A){b, j});

  45:         }

  46:         sort(buf.begin(), buf.end());

  47:         int end = 0, now = 0, ans = 0;

  48:         for (int i = 0; i < n; i++)

  49:         {

  50:             now += buf[i] . b;

  51:             end = max(end, now + buf[i] . j);

  52:         }

  53:         printf("Case %d: %d\n", count++, end);

  54:     }

  55:     return 0;

  56: }

UVa 11729 Commando War 突击战的更多相关文章

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

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

  2. 贪心 UVA 11729 Commando War

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

  3. 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 ...

  4. 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 ...

  5. &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 ...

  6. UVa 11729 - Commando War

    [题目翻译]: 题目分析:因为任务是可以并行的执行,所以直觉上是花费时间长的任务优先去部署.但是这到题目还给你交待任务的时间,所以容易让人想多了. 不管有没有交待任务的时间,对于任务x和y,只可能有两 ...

  7. UVa 11729 Commando War 【贪心】

    题意:有n个部下,交待每个部下完成他相应的任务需要bi的时间,然后完成这项任务需要ji的时间, 选择交待任务的顺序,使得总的花费的时间最少 因为不管怎么样,交待所需要的n*bi的时间都是要花费的, 然 ...

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

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

  9. Commando War

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

随机推荐

  1. MVC调试时遇到的URL问题

    最近接手一个项目时遇到了点问题,事情是这样的,本人拿到源码准备F5准备试跑看一下,原本是应该打开 http:/localhost/Home/Login,结果程序直接跳到 http://localhos ...

  2. c&num; socket 解决粘包,半包

    处理原理: 半包:即一条消息底层分几次发送,先有个头包读取整条消息的长度,当不满足长度时,将消息临时缓存起来,直到满足长度再解码 粘包:两条完整/不完整消息粘在一起,一般是解码完上一条消息,然后再判断 ...

  3. HBase读写路径的工作机制

    出处:http://wuyudong.com/1946.html HBase 写路径工作机制 在HBase 中无论是增加新行还是修改已有的行,其内部流程都是相同的.HBase 接到命令后存下变化信息, ...

  4. Linux下做软RAID

    1.查看有多少块硬盘可用#fdisk -l嗯,一般而言,留下系统盘不动,其它的盘如果大小相同的话,统统合起来做一个raid. 2.决定做什么类型的raid.raid-0.raid-1.raid-5?如 ...

  5. vc&plus;&plus;编程之在程序中加入网址链接

    在vc++对话框编程中,我们处于某种需要(介绍自己的软件或者自己的博客)可以在对话框上增加一个网址链接,用户只要一点击,就进入了相应的网页,我在此演示下如何完成. 1 打开编译器,我们新建一个基于对话 ...

  6. css解决IE6、Chrome、ff 浏览器position&colon;fixed&semi;和闪动问题

    首先说下开发模式,刚刚开始接触,基本沿用web端开发方式,目前开发模式上没有找到的适合的,现在基本这样:1,电脑nginx配置服务器3,电脑和手机连同一个局域网,2,android root 和 ip ...

  7. php用百度地图API进行IP定位和GPS定位

    <?php /** * 根据地理坐标获取国家.省份.城市,及周边数据类(利用百度Geocoding API实现) * 百度密钥获取方法:http://lbsyun.baidu.com/apico ...

  8. Linux:日期用法,及格式定义

    在shell脚本中经常会需要获取当前日期的地方,linux的系统时间在shell里是可以直接调用系统变量: 获取今天时期---`date +%Y%m%d` 或 `date +%F` 或 $(date ...

  9. cassandra 如何写数据以及放置副本

    application发送数据到server application 发送请求到server 根据设置的load balance 规则从cluster中挑选一个coordinator,一般使用轮询即可 ...

  10. sql嵌套查询

    嵌套查询的意思是,一个查询语句(select-from-where)查询语句块可以嵌套在另外一个查询块的where子句中,称为嵌套查询.其中外层查询也称为父查询,主查询.内层查询也称子查询,从查询. ...