这个贪心有什么问题吗
查看原帖
这个贪心有什么问题吗
630929
Dxy2003楼主2023/1/13 16:36
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
struct node
{
	int l, r;
}e[100001];
bool cmp(node &a,node &b)
{
	if (a.r == b.r)
	{
		return a.l < b.l;
	}
	return a.r < b.r;
}
signed main()
{
	int n;
	int ans=0,p=0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> e[i].l >> e[i].r;
	}
	sort(e, e + n , cmp);
	for (int i = 0; i < n; i++)
	{
		if ((2 * i + 1 - n) < 0)
		{
			ans += (2 * i + 1 - n) * e[i].r;
			p = e[i].r;
		}
		else
		{
			if (e[i].l <= p)
			{
				ans += (2 * i + 1 - n) * p;
			}
			else ans += (2 * i + 1 - n) * e[i].l;
		}
	}
	cout << ans*2;
	return 0;
}

基本想法就是让权值为负的尽量大,权值为正的尽量小。 但是最后只AC了三个点

2023/1/13 16:36
加载中...