社区讨论
萌新求助,,样例过了,但是提交一堆mle
P2240【深基12.例1】部分背包问题参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lobchjt9
- 此快照首次捕获于
- 2023/10/29 18:45 2 年前
- 此快照最后确认于
- 2023/11/04 00:30 2 年前
CPP
#include <stdio.h>
double h[100];
int m[100],v[100];
void swap(int*x,int*y)
{
int tem=*x;
*x=*y;
*y=tem;
}
void swap2(double*x,double*y)
{
double tem=*x;
*x=*y;
*y=tem;
}
void Quicksort(int L,int R)
{
if(L>=R)
return;
int i=L-1,j=R+1,p=h[(i+j)/2];
while(i<j)
{
do i++;while(h[i]<p);
do j--;while(h[j]>p);
if(i<j)
{
swap2(&h[i],&h[j]);
swap(&m[i],&m[j]);
swap(&v[i],&v[j]);
}
}
Quicksort(L,j);
Quicksort(j+1,R);
}
int main()
{
int n,t,i,L=0,t1=0;
double v1=0;
scanf("%d%d",&n,&t);
for(i=0;i<n;i++)
{
scanf("%d %d",&m[i],&v[i]);
h[i]=(double)v[i]/m[i];
}
Quicksort(L,n-1);
i=n-1;
while(t-0>-0.000000001&&i>=0)
{
if(t-m[i]>-0.0000001)
v1+=m[i]*h[i],t-=m[i],i--;
else if(t-m[i]<-0.000000000001)
{
v1+=h[i]*(t-t1);
break;
}
}
printf("%.2f",v1);
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...