第一个案例没过,求大佬指导
查看原帖
第一个案例没过,求大佬指导
659596
woshisilong楼主2022/3/16 20:55
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 105;
int n,t;
double temp[N];//存放性价比  "价格 / 重量"
PII c[N],tmp[N];//coin硬币(重量,价值) 和 归并排序用的数组


void merge_sort(PII a[],int l,int r){//对coin根据性价比归并排序
	if (l >= r)	return;
	int mid = l + r >> 1;
	merge_sort(a,l,mid),merge_sort(a,mid+1,r);
	int i = l,j = mid + 1,k = 0;
	while (i <= mid && j <= r)
		if ((double)a[i].y/a[i].x >= (double)a[j].y/a[j].x) 
			tmp[k++] = a[j++];
		else
			tmp[k++] = a[i++];
	while (i <= mid)	tmp[k++] = a[i++];
	while (j <= r)	tmp[k++] = a[j++];
	for (i = l,j = 0;i <= r;i++,j++)
		a[i] = tmp[j];
}

int main(){
	int size = 0;
	double worth = 0.0;
	scanf("%d%d",&n,&t);
	for (int i = 1;i <= n;i++){
		scanf("%d%d",&c[i].x,&c[i].y);
	}
	merge_sort(c,1,n); // 对硬币按性价比升序排序
	for (int i = 1;i <= n;i++)
		temp[i] = (double)c[i].y/c[i].x;
	int idx = 0;
	for (int i = n;i;i--){
		if (size + c[i].x >= t){//若背包加上当前这堆硬币超重就退出
			idx = i;
			break;
		}
		size += c[i].x;
		worth += c[i].y;	
	}
	int last = t - size;
	if (last > 0)
		worth += (double)c[idx].y/c[idx].x * last;
	printf("%.2f",worth);
	return 0;
}
2022/3/16 20:55
加载中...