第一次过T4好开心啊啊啊啊啊啊啊啊啊啊啊啊

用户头像 发布于 2025-10-19 91 次阅读


洛谷用户ID1808888选手第一次过T4。过的题是NOIP2015普及组T4,洛谷上是P2672,一道贪心题。洛谷上不能发题解,发在这里。我是特大垃圾袋。

#include <bits/stdc++.h>
using namespace std;
/*疲劳度和:Σa+2*smax 
对于x家的情况,可以有两种情况最长:
1.老老实实走完所有前x大的家
2.舍弃较为小的,换取更多路程
*/
int maxs[100005],suma[100005],maxx[100005];
int n; 
struct pl
{
	int s;
	int a;
}t[100005];
bool cmp(pl x,pl y)
{
	return x.a>y.a;
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>t[i].s;
	} 
	for (int i=1;i<=n;i++)
	{
		cin>>t[i].a;
	} 
	sort(t+1,t+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		maxs[i]=max(maxs[i-1],t[i].s);
		suma[i]=suma[i-1]+t[i].a;
	}
	for (int i=n;i>=1;i--)
	{
		maxx[i]=max(2*t[i].s+t[i].a,maxx[i+1]);
	}
	for (int i=1;i<=n;i++)
	{
		int ans;
		ans=max((2*maxs[i]+suma[i]),(suma[i-1]+maxx[i+1]));
		cout<<ans<<endl;
	}
	return 0;
}
一名爱捣鼓自己网站的初中生~
最后更新于 2025-10-19