洛谷用户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;
}
Comments NOTHING