社区讨论

这题为什么要用01背包啊?

P4377[USACO18OPEN] Talent Show G参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2mdnt3
此快照首次捕获于
2023/10/23 16:12
2 年前
此快照最后确认于
2023/10/23 16:12
2 年前
查看原帖
现在我知道了f(x)=求和(t-w*x)
如果f(x)>0 则left=mid,否则right=mid;
我直接将t-w*x排序,把它们从大到小加起来直到满足重量>w.为什么最后会wrong呢?
CPP
#include<iostream>
using namespace std;
struct node{
	int ww;
	int tt;
}cow[300];
double coww[300],ww[300];
int n,w;
void ssort(double mid){
	for(int i=1;i<=n;i++){
		coww[i]=cow[i].tt-mid*cow[i].ww;
		ww[i]=cow[i].ww;
	}
	for(int i=1;i<n;i++)
	for(int j=1;j<n-i;j++){
		if((coww[j]<coww[j+1]) || (coww[j]==coww[j+1] && ww[j+1]>ww[j]) ){
			double wq=coww[j+1];
			coww[j+1]=coww[j];
			coww[j]=wq;
			wq=ww[j+1];
			ww[j+1]=ww[j];
			ww[j]=wq;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>w;
	double left=0,right=0;
	for(int i=1;i<=n;i++){
		cin>>cow[i].ww>>cow[i].tt;
		double qq=double(cow[i].tt)/double(cow[i].ww);
		right=max(right,qq);
	}
	while(right-left>0.000001){
		double mid=(left+right)/2;
		ssort(mid);
		int weight=0;
		int index=0;
		double a=0;
		while(weight<w || coww[index+1]>=0){
			weight+=ww[++index];
			a+=coww[index];
		}
		if(a>0) left=mid;
		else right=mid;
	}
	int aa=(left+right)/2*1000;
	cout<<aa;
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...