AOJ 802.运输宝物

G. 运输宝物

Time Limit: 1000 ms   Case Time Limit: 1000 ms   Memory Limit: 64 MB
Total Submission: 53   Submission Accepted: 22

Description

众所周知,“西瓜”是大名鼎鼎的江洋大盗。有一次他偷到了一批宝库。
这批宝物共有n个,他一共有k个箱子。他只能用这些箱子把这些宝物运出去,为了保证运输安全,他不会把两个以上的宝物装入同一个箱子(一个箱子只能装1个或者2个宝物)。这些宝物的大小分别是s(1)、s(2)、s(3)……s(n)。(题目给出的重量保证是非降序,即s(i-1)<=s(i) 对于任何i>1)。
装进宝物后,每个箱子的容量要大于或者等于所装的宝物大小之和。为了规格统一,这些箱子每个的容量要一致。为了降低运费,箱子的容量要尽可能小。“西瓜”想要知道,在能运走的情况下,箱子容量最小是多少。

Input

多组输入
先输入n和k (1≤n≤2·k≤100 000),n是宝物数量,k是箱子数量。
下一行输入空格分隔的n个整数, s1,s2,...,sn (1≤s1≤s2≤...≤sn≤1 000 000),代表这些宝物的重量。

Output

输出一个整数,代表这些箱子容量的最小值。

Sample Input

Original Transformed
4 3
2 3 5 9

Sample Output

Original Transformed
9

只需将宝物按照从大到小装箱,然后再将剩下的宝物按照从大到小装入从小到大的箱子中

最后求出所有箱子中最大值即可

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <memory>
 6 #include <stack>
 7 #include <queue>
 8 #include <set>
 9 #include <algorithm>
10 #include <map>
11 #include <vector>
12 using namespace std;
13
14 #define debug 0
15
16 /*
17 By:OhYee
18 Github:OhYee
19 Email:[email protected]
20 Blog:http://www.cnblogs.com/ohyee/
21
22 かしこいかわいい?
23 エリーチカ!
24 要写出来Хорошо的代码哦~
25 */
26 #define REP(n) for(int o=0;o<n;o++)
27 const int maxn=100005;
28 const int maxk=50005;
29
30 int n,k;
31 int s[maxn];
32
33 bool Do(){
34     if(scanf("%d%d",&n,&k)==EOF)
35         return false;
36     REP(n)
37         scanf("%d",&s[o]);
38
39     if(k>=n){
40         printf("%d\n",s[n-1]);
41         return true;
42     }
43
44     int w[maxk];
45     REP(k){
46         w[o]=s[n-k+o];
47     }
48
49     #if debug
50     REP(n)
51         printf("s[%d]=%d\n",o,s[o]);
52     printf("\n");
53     REP(k)
54         printf("w[%d]=%d\n",o,w[o]);
55     printf("\n");
56     #endif // debug
57
58     for(int i=0;i<n-k;i++){
59         w[i]+=s[n-k-1-i];
60     }
61
62
63
64     int M=w[0];
65     REP(k){
66         M=max(M,w[o]);
67     }
68     #if debug
69     REP(k)
70         printf("w[%d]=%d\n",o,w[o]);
71     #endif // debug
72     printf("%d\n",M);
73
74     return true;
75
76 }
77
78
79
80 int main(){
81     #if debug
82     freopen("in.txt","r",stdin);
83     #endif
84     while(Do());
85     return 0;
86 }
时间: 04-09

AOJ 802.运输宝物的相关文章

[luogu P1967][NOIp2013]P1967 货车运输

题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 输入输出格式 输入格式: 输入文件名为 truck.in. 输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道 路. 接下来 m 行每行 3 个整数 x. y. z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z

bzoj1003: [ZJOI2006]物流运输

dp+最短路.暴力枚举就可以了.O(n3logn).样例中m=n然后测样例过了.然后 54行习惯性的dis[n]然后就WA了!!!. #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #de

wpa_supplicant 和 802.11g WPA 认证的配置

# cd /etc/init.d# ln -s net.lo net.eth0 默认的接口名是 wlan0,让它开机时自动 up:cp /etc/init.d/net.lo /etc/init.d/net.wlan0 ifconfig wlan0 up 根据接入点设置编辑 /etc/wpa_supplicant/wpa_supplicant.conf: ctrl_interface=/var/run/wpa_supplicantctrl_interface_group=wheelupdate_c

listing界面与运输渠道的优化操作

在此前的<亚马逊站内引流>系列文章中,小编已经将Skyla细分的亚马逊站内引流八大渠道(变体.广告.Feedback.Review.完美listing界面.促销.运输渠道和销量)中的"变体.广告.和Feedback&Review"四个方式的具体操作整理成文. 本文将把"完美listing界面"与"运输渠道"并在一起详细讲解. 如何做出完美的listing界面 listing界面做的好,对于吸引流量.增加消费者的购买欲望.提高转

[HNOI2014]米特运输

题目描述 米特是D星球上一种非常神秘的物质,蕴含着巨大的能量.在以米特为主要能源的D星上,这种米特能源的运输和储存一直是一个大问题. D星上有N个城市,我们将其顺序编号为1到N,1号城市为首都.这N个城市由N-1条单向高速通道连接起来,构成一棵以1号城市(首部)为根的树,高速通道的方向由树中的儿子指向父亲.树按深度分层:根结点深度为0,属于第1层:根结点的子节点深度为1,属于第2层:依此类推,深度为i的结点属于第i+l层. 建好高速通道之后,D星人开始考虑如何具体地储存和传输米特资源.由于发展程

BZOJ 1003: [ZJOI2006]物流运输trans

二次联通门 : BZOJ 1003: [ZJOI2006]物流运输trans /* BZOJ 1003: [ZJOI2006]物流运输trans Spfa + Dp Spfa预处理出i到j天的最小花费 然后N^2 dp即可 */ #include <cstdio> #include <iostream> #include <cstring> #include <queue> #define INF 1e6 const int BUF = 12312313;

【NOIP2013货车运输】

描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路.每一条道路对车辆都有重量限制,简称限重.现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物. 格式 输入格式 第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路. 接下来 m 行每行 3 个整数 x.y.z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路.注意:x 不等于 y,两座城市之间可能有多条道路. 接

[ZJOI2006]物流运输

Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 8278  Solved: 3486 Description 物流公司要把一批货物从码头A运到码头B.由于货物量比较大,需要n天才能运完.货物运输过程中一般要转 停好几个码头.物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪.由于各种 因素的存在,有的时候某个码头会无法装卸货物.这时候就必须修改运输路线,让货物能够按时到达目的地.但是 修改路线是一件十分麻烦的事情,会带来额

P1776 宝物筛选_NOI导刊2010提高(02)(背包的二进制优化)

题目描述 终于,破解了千年的难题.小FF找到了王室的宝物室,里面堆满了无数价值连城的宝物……这下小FF可发财了,嘎嘎.但是这里的宝物实在是太多了,小FF的采集车似乎装不下那么多宝物.看来小FF只能含泪舍弃其中的一部分宝物了……小FF对洞穴里的宝物进行了整理,他发现每样宝物都有一件或者多件.他粗略估算了下每样宝物的价值,之后开始了宝物筛选工作:小FF有一个最大载重为W的采集车,洞穴里总共有n种宝物,每种宝物的价值为v[i],重量为w[i],每种宝物有m[i]件.小FF希望在采集车不超载的前提下,选