题目分析:这个如何贪心,很难想!!!有忍不住参照别人的思想了!!!!!
但是我感觉我下面的哪个WA一直的思想也对不知道为啥过不了!!!
思想:如果是两件的话:
a1 , b1和a2 ,b2.... 瞬时所占体积的最大值为,a1+b2 或者 b1+a2,肯定选择较小的哪个来放...
在推广的n个
/*****贪心***/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int a,b;
}arr[2000];
int cmp(node x,node y)
{
return x.a+y.b<x.b+y.a;
}
int main()
{
int n,v,t;
scanf("%d",&t);
int vis[2000];
while(t--)
{
//scanf("%d",&v,&n);//脑残了****,检查了好长时间,没发现 少了个%d
scanf("%d %d",&v,&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&arr[i].a,&arr[i].b);
}
sort(arr+1,arr+1+n,cmp);
memset(vis,0,sizeof(vis));
int flag=1;
for(int i=1;i<=n;i++)
{
if(v>=arr[i].b)
v-=arr[i].a;
else
{
flag=0;
break;
}
}
if(flag==1)
printf("Yes\n");
else
printf("No\n");
}//*************************while
system("pause");
return 0;
}
不知道wa在那里????????????有哪位大神路过,麻烦指出,小弟不甚感激
/*****贪心****
先放能放的中,所占体积最小的哪个物品
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int a,b;
}arr[2000];
int cmp(node x,node y)
{
if(x.b==y.b)
return x.a<y.a;//升序
else
return x.b>y.b;//降序
}
int main()
{
int n,v,t;
scanf("%d",&t);
int vis[2000];
while(t--)
{
//scanf("%d",&v,&n);//脑残了****,检查了好长时间,没发现 少了个%d
scanf("%d %d",&v,&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&arr[i].a,&arr[i].b);
//cin>>arr[i].a>>arr[i].b;
//printf("%d %d***\n",arr[i].a,arr[i].b);
}
sort(arr+1,arr+1+n,cmp);
/*for(int i=1;i<=n;i++)
{
printf("%d %d***\n",arr[i].a,arr[i].b);
}*/
memset(vis,0,sizeof(vis));
int flag=1,temp,tempA;
for(int k=1;k<=n;k++)
{
temp=0,tempA=10000;
for(int i=1;i<=n;i++)//每次选
if(vis[i]==0)
{
if(v==arr[i].b)//刚好
{
temp=i;
break;//开始少了
}
else if(v-arr[i].b>0 && tempA>arr[i].a)//寻找能放的物品中,占体积最小的
{
temp=i;
tempA=arr[i].a;
}
}
if(temp!=0)
{
v-=arr[temp].a;
vis[temp]=1;
}
else
{
flag=0;
break;
}
}
if(flag==1)
printf("Yes\n");
else
printf("No\n");
}//*************************while
system("pause");
return 0;
}