杭电OJ 3177题老是WA,/*思路：贪心算法,我们每次搬运想到就是使剩余的洞穴空间尽量大,当有两件物品时,有如下信息A a1 b1B a2 b2加入先搬A,则搬运过程中瞬间占用空间最大为a1+b2,如果先搬运B,则
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/27 09:59:06
杭电OJ 3177题老是WA,/*思路：贪心算法,我们每次搬运想到就是使剩余的洞穴空间尽量大,当有两件物品时,有如下信息A a1 b1B a2 b2加入先搬A,则搬运过程中瞬间占用空间最大为a1+b2,如果先搬运B,则
杭电OJ 3177题老是WA,
/*
思路：贪心算法,我们每次搬运想到就是使剩余的洞穴空间尽量大,当有两件物品时,有如下信息
A a1 b1
B a2 b2
加入先搬A,则搬运过程中瞬间占用空间最大为a1+b2,如果先搬运B,
则这一个瞬间最大占用体积为a2+b1,我们想使剩下的体积尽量大,所以我们选择min(a1+b2,a2+b1),如果先选A,
则有a1+b2b2-a2,所以我们可以看出,应该先选搬运体积和本身体积差值最大的贪心,由此得到最优搬运顺序!
*/
#include
typedef struct node{
int a;
int b;
int c;
}Node;
int quicksort(Node a[],int s,int e);
int main()
{
int v,n;
int t;
int i;
int flag;
Node a[1000];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&v,&n);
for(i=0;iv)flag=0;
else v-=a[i].a;
}
//开始逐个放进洞里.
if(flag)printf("Yes\n");
else printf("No\n");
}
return 0;
}
int quicksort(Node a[],int s,int e)
{
int f,b,key;
Node m,n;
f=s+1;
b=e;
key=a[s].c;
n=a[s];
if(s>=e)return 0;
while(f
杭电OJ 3177题老是WA,/*思路：贪心算法,我们每次搬运想到就是使剩余的洞穴空间尽量大,当有两件物品时,有如下信息A a1 b1B a2 b2加入先搬A,则搬运过程中瞬间占用空间最大为a1+b2,如果先搬运B,则
排序法确实有问题
while(f