题解 | #牛牛的背包#

思路很顺畅，经典贪心

但是可能是我审题问题，基本上我能想到的所有情况我都能通过，但是通过率只有30%

这里分享下我的思路，也麻烦大伙看看有什么问题！

#include <math.h>
#include <algorithm>
#include <cstring>
using namespace std;
struct product {
	int num;
	bool type=false;//不存在这个序号的taste
	long taste;
	bool positive=false;// 判断输入的taste是否为正数
}a[100];
int cmp(product a, product b)
{
	return a.taste > b.taste;
}
int main() {
	int n,i=0,x;
	long sum = 0,count=0;
	cin >> n;//第一行 输入：总共的物品数量
	while (i < n)
	{
		cin >> a[i].num;
		a[a[i].num].type = true;
		i++;
	}//第二行 输入type：我这里用数组下标直接暗示类型
	i = 0;
	while (i < n)
	{
		cin >> a[a[i].num].taste;
		if (a[a[i].num].taste > 0)
			a[a[i].num].positive = true;
		i++;
	}//第三行 输入taste：这里设计所有taste值，由于x*y的y值是总和，下标不影响
	//sort(a, a + n, cmp);
	for (int j = 0; j < 50; j++)
	{
		if (a[j].positive&&a[j].type)
		{
			sum += a[j].taste;
			count++;
			a[j].type=false;
		}
	}// 正值直接计入就行
	for (int j = 0; j < 50; j++)
	{
		if ((!a[j].positive)&&(a[j].type))
		{
			if (a[j].taste * (count + 1) + sum > 0)
				//列式主题，这种情况下可以得到最大值
			{
				sum = sum + a[j].taste;
				count++;
			}
		}
	}
	long all = sum * count;
	if (all >= 0)//正值直接输出，负值可以通过不进行选择，直接输出0
		cout << all;
	else
		cout << 0;

	return 0;
}