50分贪心求纠正思路
查看原帖
50分贪心求纠正思路
1088617
Kevin_Mu楼主2024/11/19 21:15

我的思路是:对每一个i,枚举j,考虑是否可以在i,j间移动泥土。但是这种算法好像不是正解,Wrong了五个点,求大佬指点为什么不行

#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn],b[maxn],n,x,y,z,ans;
int main()
{
	cin>>n>>x>>y>>z;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		a[i] -= b[i];
		//若a[i]为正,则a[i]--消耗y 
		//若a[i]为负,则a[i]++消耗x 
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]>0)
		{
			for(int j=i+1;j<=n;j++)//考虑每一个j,若a[j]与a[i]异号,则可以移动泥土 
			{
				if(z*(j-i)>(x+y)||a[i]==0)//如果移动泥土不如直接+/-划算,或者已经达到目标状态,跳出循环 
					break;
				if(a[j]<0)
				{
					int num = min(a[i],-a[j]);//可移动泥土数量 
					a[j] += num;
					a[i] -= num;
					ans += num*z*(j-i);
				}
			}
			ans += a[i] * y;//剩下的泥土全都要移除 
		}
		else if(a[i]<0)
		{
			for(int j=i+1;j<=n;j++)//考虑每一个j,若a[j]与a[i]异号,则可以移动泥土
			{
				if(z*(j-i)>(x+y)||a[i]==0)//如果移动泥土不如直接+/-划算,或者已经达到目标状态,跳出循环
					break;
				if(a[j]>0)
				{
					int num = min(-a[i],a[j]);//可移动泥土数量 
					a[j] -= num;
					a[i] += num;
					ans += num*z*(j-i);
				}
			}
			ans += (-a[i]) * x;//剩下的泥土全都要加上 
		}
	}
	cout<<ans;
	return 0;
}

样例附上:输入

20 12 11 1
10 3
1 3
4 8
6 10
3 3
9 10
8 4
7 2
3 10
4 2
10 5
8 9
5 6
1 4
7 2
1 7
4 3
1 7
2 6
6 5

输出

157
2024/11/19 21:15
加载中...