AOJ 802.运输宝物

153

题目



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  


4 3
2 3 5 9



Sample Output  


9


题解



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

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


代码



#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <memory>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
 
#define debug 0
 
/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#define REP(n) for(int o=0;o<n;o++)
const int maxn=100005;
const int maxk=50005;
 
int n,k;
int s[maxn];
 
bool Do(){
    if(scanf("%d%d",&n,&k)==EOF)
        return false;
    REP(n)
        scanf("%d",&s[o]);
 
    if(k>=n){
        printf("%d\n",s[n-1]);
        return true;
    }
 
    int w[maxk];
    REP(k){
        w[o]=s[n-k+o];
    }
 
   if debug
    REP(n)
        printf("s[%d]=%d\n",o,s[o]);
    printf("\n");
    REP(k)
        printf("w[%d]=%d\n",o,w[o]);
    printf("\n");
   endif // debug
 
    for(int i=0;i<n-k;i++){
        w[i]+=s[n-k-1-i];
    }
 
 
 
    int M=w[0];
    REP(k){
        M=max(M,w[o]);
    }
   if debug
    REP(k)
        printf("w[%d]=%d\n",o,w[o]);
   endif // debug
    printf("%d\n",M);
 
    return true;
 
}
 
 
 
int main(){
   if debug
    freopen("in.txt","r",stdin);
   endif
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论