P2672 [NOIP2015 普及组] 推销员 day15

这道题非常牛逼啊！

最开始想到了个n^2 然后实在没办法去看题解

学到了很多

首先我们有且仅有 2 种 方式 get 到最优解 

1是直接选疲惫值最高的 2是也是和1一样 可是要丢掉一个最低的 换取后面的权重最大的一个点

1很好想 我最开始也是想了很久2 难道不能换2个 3个点嘛 

接下来我来证明一下啊！(以两个点为例

要是我们get了两个后面的点 am an 丢弃的两个点为 ax ax-1

交换之后的值为 am+an+max(dis[am],dis[an]) 

要是an > am&&dis[an]>dis[am]

那我们交换an之后才是最优解 因为我们从大到小 get点 而 am一定小于 ax-1

要是 an>am&&dis[an]<dis[am]

再分为两种情况啊 那就是把两个不等式加起来

1.an+dis[an]>am+dis[am]   这种情况 确实是有可能舍去 ax-1和ax的 可是因为每次都计入一次结果 这个也就可以看成两次舍去ax

2.an+dis[an]<am+dis[am]   这种情况就不用说了am次序更大且权重更大 那么每次都会选择am

注意：

下面代码中

我们先按照疲惫值sort

sum[]为s[]前缀和

q[]为排序后的前i个值里对应的最大距离；

h[]为排序后的后面的值里最值得选的一个点的值；

h是可能变化的！

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 1e4+10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int s[N],a[N],q[N],sum[N],h[N];
pair<int,int>p[N];
signed main(){
    fast
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        p[i].first=a[i];
        p[i].second=s[i];
    }
    sort(p+1,p+n+1,greater<>());
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+p[i].first;
        q[i]=max(p[i].second*2,q[i-1]);
    }
    for(int i=n;i>=1;i--)h[i]=max(h[i+1],2*p[i].second+p[i].first);
    for(int i=1;i<=n;i++)cout<<max(sum[i]+q[i],sum[i-1]+h[i])<<endl;
    return 0^0;
}