注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1197.决战诺曼底  

2011-12-02 20:52:00|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1197.决战诺曼底
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 236 (81 users)         Accepted: 95 (73 users)
[ My Solution ]

Description
        诺曼底一战事关整个战局的成败,因此盟军最高将领决定拟定一个能尽可能减少伤亡的登陆计划。其中有一个涉及到乘船问题。盟军利用一种快艇从战舰冲到海岸,这个过程是相当危险的,因此将领们想尽可能的减少快艇数量。也就是要用尽量少的快艇把士兵们送过去。其中这种快艇的载重为C,最多能坐两位士兵。现在已知有n位士兵,第i位士兵的重量为w[i]。现在要你求出最少要多少部快艇才能把全部士兵送过去。

Input
第一行是两个正整数C和n, 分别表示一部快艇的载重和士兵数,1 <= C , n <= 1000000。
第二行有n个正整数,第i个w[i]表示第i个士兵的体重。w[i] <= C。

Output
输出最少需要的快艇数。

Sample Input
7 5
2 3 4 5 6

Sample Output
3

Source
sauce @ xmu
 
就一个贪心,先排序,然后再把最小的和最大的相加。如果大于c则只能一个士兵上船,否则两个士兵都可以上船。处理到最后。就是总共需要的船只了!
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int w[1000000];
int main()
{
 int n, c, i, j; 
 scanf("%d%d", &c, &n);
 for(i = 0; i < n; i++)
  scanf("%d", &w[i]);
 sort(w, w + n);
 int cnt = 0;
 for(i = 0, j = n - 1;;)
 {
  if(i == j){ cnt++; break;}
  if(w[i] + w[j] <= c)
  {
   cnt++;
   if(i + 1 == j) break;
   i++;j--;
   
  }
  else
  {
   cnt++;j--;
  }
 }
 printf("%d\n", cnt);
return 0; 
}
  评论这张
 
阅读(137)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017