社区讨论

萌新求助,,样例过了,但是提交一堆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 条回复,欢迎继续交流。

正在加载回复...