这是一道贪心的题，首先输入完数据后排一个序（从小到大），用一个标记数组来对纪念品进行一个标记。我们需要先拿出一个纪念品，去跟其它的纪念品进行配对：原因是要求组合最少，那么两个就是最优解。在剩下的纪念品中找出不会超出限制，并且为最大的，这就是目前的最优解。代码如下
//未排序
#include<bits/stdc++.h>
using namespace std;
int w,n,a[30005],ans,k[30005];
int main(){
scanf("%d %d",&w,&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(k[i]==1) continue;
int sum=0,l=0;
for(int j=i+1;j<=n;j++){
if(k[j]==0)
if(a[j]+a[i]<=w)
if(a[j]>sum){
l=j;
sum=a[j];
}
}
ans++;
k[l]=1;
k[i]=1;
}
printf("%d",ans);
return 0;
}
等等！！！
温馨提示，此代码100%会超时:why?因为每一次找第二个数时，都会循环一次，那么时间就自然长了 那么我们开始优化一下， 循环变量可以从最后一位开始，只要不超出限制，它就是当前的最优解。 （好好想一想......），想好了再看代码
#include<bits/stdc++.h>
using namespace std;
int w,n,a[30005],ans,k[30005];
int main(){
scanf("%d %d",&w,&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
if(k[i]==1) continue;
int sum=0,l=0;
for(int j=n;j>=i+1;j--){
if(k[j]==0)
if(a[j]+a[i]<=w){
l=j;
break;
}
}
ans++;
k[l]=1;
k[i]=1;
}
printf("%d",ans);
return 0;
}
共 2 条回复
Orz，太强了，爆切NOIP2007普及组
棒！！！