解题思路

主要来源于LCY算法入门培训第2讲

根据每堆金币单位重量的价值进行排序然后从最大价值开始填满背包库存

既然允许金币分割那就开始贪呗(

代码实现(第一次)

祖传冒泡(因为数据组数不算太大所以冒泡排序先写着也是可以的)

#include <bits/stdc++.h>
using namespace std;

int T, n;
double ans;

//std::swap也是能用的 当时写上头了
void swap(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

int main() {
    //输入数据组数和背包容量
	cin >> T >> n;
	int a[T], b[T];
   	//开俩数组分别来存每堆金币的重量和
	for (int i = 0; i < T; i++) {
		cin >> a[i] >> b[i];
	}
	//祖传冒泡 通过比较相邻两堆金币的价值进行 降序 排序
	for (int i = 0; i < T - 1; i++) {
		for (int j = i; j < T - 1; j++) {
			if (double(b[j] / a[j]) < double(b[j + 1] / a[j + 1])) {
				swap(a[j], a[j + 1]);
				swap(b[j], b[j + 1]);
			}
		}
	}
    //金币堆现在降序排序 也就是说我们可以从顶上开始吃(
    //开始扫描所有金币 如果包的容量n大于当前金币a[i]则全部收下,并且包的容量n减去当前金币的重量b[i],ans加上当前金币的价值
    
	for (int i = 0; i < T; i++) {
		if (n >= a[i]) {
			n -= a[i];
			ans += b[i];
		} else {
			ans += double(b[i] / a[i]) * n;
			break;
            //不加break会让程序出错
		}
	}
    //完美收官(误)
	printf("%.2lf", ans);
	return 0;
}

~~是不是感觉看上去像模像样的?有种快要AC的错觉了是把?~~

不需要数据，double(b[j] / a[j]) < double(b[j + 1] / a[j + 1]) 显然是错的。

double()是强制转换类型了但是呢? b[j]/a[j]仍然是"整数除以整数" 这东西能排序但只能排一点点

比如这东西就分辨不出3 7和3 6的价值哪个更高

在不断尝试中我发现问题主要还是出在排序上

当时没想那么多于是我改了改排序和swap:

void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}
//省略其他部分
for (int i = 0; i < T - 1; i++) {
		for (int j = i; j < T - 1; j++) {
			double t1 = (double)b[j] / a[j];
			double t2 = (double)b[j + 1] / a[j + 1];
			if (t1 < t2) {
				swap(a + j, a + j + 1);
				swap(b + j, b + j + 1);
			}
		}
	}

但不幸的是这玩意仍然有问题于是我直接开了第三个double数组直接拿来存每堆金币的价值

AC代码

#include <bits/stdc++.h>
using namespace std;

//swap改回来了
void swap(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

int main() {
	int T, n;
	double ans = 0;
	cin >> T >> n;
	int a[T], b[T];
    //开新的数组
	double c[T];

	for (int i = 0; i < T; i++) {
		cin >> a[i] >> b[i];
        //给新的数组赋值
		c[i] = double(b[i]) / double(a[i]);
	}
	for (int i = 0; i < T - 1; i++) {
		for (int j = 0; j < T - 1; j++) {
			if (c[j] < c[j + 1]) {
                //三个一起换
				swap(a[j], a[j + 1]);
				swap(b[j], b[j + 1]);
				swap(c[j], c[j + 1]);
			}
		}
	}
	for (int i = 0; i < T; i++) {
		if (n >= a[i]) {
			n -= a[i];
			ans += b[i];
		} else {
			ans += double(b[i]) / double(a[i]) * n;
			break;
		}
	}
    //完美(
	printf("%.2lf", ans);
	return 0;
}

写完代码10分钟改代码100分钟

如何避免出现开三个数组同时进行排序这样的惨案?(AC代码)

使用结构体就好了(笑)

#include <bits/stdc++.h>
using namespace std;

struct Gold {
	int w;
	int p;
	double ppw;
};

//降序按照ppw(price_per_weight)排列
bool cmp(Gold a, Gold b) {
	return a.ppw > b.ppw;
}

void swap(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

int main() {
	double ans = 0;
	int T, n;

	scanf("%d %d", &T, &n);
	struct Gold g[T];
    
	for (int i = 0; i < T; i++) {
		scanf("%d %d", &g[i].w, &g[i].p);
		g[i].ppw = double(g[i].p) / double(g[i].w);
	}
    
	sort(g, g + T, cmp);
//	for (int i = 0; i < T; i++) {
//		cout << g[i].ppw << " ";
//	}
    
	for (int i = 0; i < T; i++) {
		if (n >= g[i].w) {
			n -= g[i].w;
			ans += g[i].p;
		} else {
			ans += g[i].ppw * n;
			break;
		}
	}
	printf("%.2lf", ans);
	return 0;
}

大体和前面的鬼东西没什么区别 ~~但是更!快!也!更!爽!~~

前面的能看懂后面这个也能懂(

THE END

洛谷P2240题解与总结

解题思路

代码实现(第一次)

AC代码

如何避免出现开三个数组同时进行排序这样的惨案?(AC代码)