Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意是说。给n个balls,k个箱子。保证（n<=2*k） 一个箱子中中最多放两个balls，size为两个balls的size之和。 所有的箱子的size都要一样。 问size最小是多少。
只要让最大的size尽可能小即可。 容易想到一组贪心策略。 可以先看有几个多出来的位置 （2*k-n） 然后把最大的几个size的ball装在多余的位置里。。更新答案。 然后对于剩下的。。。最小的和最大的一组状进去。。。扫一遍更新答案。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月02日 星期三 00时00分22秒
4File Name :code/cf/#334/B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,k;
35int s[N];
36int a[N];
37int main()
38{
39 #ifndef ONLINE_JUDGE
40 freopen("code/in.txt","r",stdin);
41 #endif
42 ms(s,0);
43 ms(a,0);
44 scanf("%d %d",&n,&k);
45 for ( int i = 1 ; i <= n ; i++)
46 scanf("%d",&s[i]);
47 int duoyu = k*2-n;
48// cout<<"duoyu:"<<duoyu<<endl;
49 int nn = n - duoyu;
50// cout<<"nn:"<<nn<<endl;
51 int ans = -1;
52 for ( int i = nn+1 ; i <= n;i++) ans = max(ans,s[i]);
53 for ( int i = 1 ; i <= nn/2 ; i++)
54 {
55 ans = max(ans,s[i]+s[nn-i+1]);
56// cout<<"i:"<<i<<" "<<s[i]<<endl;
57// cout<<"nn-i+1"<<nn-i+1<<" s[nn-i+1]:"<<s[nn-i+1]<<endl;
58 }
59 cout<<ans<<endl;
60
61
62 #ifndef ONLINE_JUDGE
63 fclose(stdin);
64 #endif
65 return 0;
66}