问题 G: 搬书
时间限制: 1 Sec 内存限制: 128 MB
提交: 576 解决: 49
[提交][状态][讨论版]
题目描述
XCQ队长要退役啦，由于队长常年刷题，机位上摆着各类算法书，一个人实在是搬不动，所以他叫来了他的小弟ZZX帮忙搬书。队长突然灵机一动，给ZZX出了一个问题。
假设机位上有n本书，每本书的体积分别为ai，那么如果使用容量为V的书包来装书最少要几个书包呢？(注意书是不可拆分的，整体要么装到一个书包，要么不装)。
ZZX(冥思苦想)： 不会呀。
XCQ： 看你这么弱，我就把问题再简化一下好啦，让每个书包只装不超过两本书, 那么用k(2 * k >= n)个体积为V的书包能否装完n本书呢？
ZZX(又是一阵冥思苦想): 队长放过我吧，实在是不会啊。
XCQ: 长江后浪推前浪， 既然如此，就把这个问题交给后浪们吧。
输入
第一行包含一个数字T(T <= 60), 表示测试数据组数。然后一空行，随后有T组数据。
每组测数据格式如下：
第一行包含三个数字n，k，V(1 <= n <= 1000000, n <= 2 * k <= 1000000, 1 <= V <= 1000000),表示有n本书，使用k个容量为V的书包。
第二行n个数,表示每本书的体积ai(ai <= 1000000)。所有数据保证给出的n个数是非递减的。
每组数据后面有一空行。
输出
每组数据输出一行, 如果能够装完所有书本输出"Yes"，否则输出"No"，引号不需要输出，注意字母大小写。
样例输入
3 4 5 8
1 5 6 8 3 2 7
3 5 7 10 5 108
15 15 20 28 38 44 46 52 69 94
样例输出
Yes
No
No 判断最后一个是否大于最大容量。然后判断k个包够不够装
#include <cstdio>
int t,n,k,v,i,j,s[],ans,flag,op;
int main()
{
scanf("%d",&t);
while(t--)
{
flag=,i=,j=;
for(scanf("%d%d%d",&n,&k,&v),i=;i<n;i++) scanf("%d",&s[i]);
if(s[n-]>v) flag=;
else if(k>=n)
{
if(s[n-]>v) flag=;
else flag=;
}
else
{
i=,j=(n-k)*-;
while(i<j)
{
if(s[i++]+s[j--]>v)
{
flag=;
break;
}
}
}
if(flag) printf("Yes\n");
else printf("No\n");
}
return ;
}