P2240部分背包,样例可过,20pts求调
  • 板块学术版
  • 楼主I_will_AKIOI我心依旧
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/3/14 19:22
  • 上次更新2023/10/23 21:33:48
查看原帖
P2240部分背包,样例可过,20pts求调
565265
I_will_AKIOI我心依旧楼主2023/3/14 19:22

传送门

#include<bits/stdc++.h>
using namespace std;
struct data {int m,v;double q;};
bool cmp(data a,data b){return a.q>b.q;}
data m[1000];
int n,s;
double ans;
int main()
{
  cin>>n>>s;
  for(int i=1;i<=n;i++)
  {
  	cin>>m[i].m>>m[i].v;
  	m[i].q=m[i].v/m[i].m*1.0;
  }
  sort(m+1,m+n+1,cmp);
  for(int i=1;i<=n;i++)
  {
	if(s-m[i].m<0)
	{
	  ans+=m[i].q*s*1.0;
	  break;
	}
	else 
	{
	  ans+=m[i].v;
	  s-=m[i].m;
	}
  }
  cout<<fixed<<setprecision(2)<<ans;
  return 0;
}
2023/3/14 19:22
加载中...