社区讨论
这题为什么要用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 条回复,欢迎继续交流。
正在加载回复...