Educational Codeforces Round 138 (Rated for Div. 2) B. Death‘s Blessing

Educational Codeforces Round 138 (Rated for Div. 2) B. Death’s Blessing

• 选择 $a[i]$ 的话，$a[i-1]+b[i],a[i+1]+b[i]$ ，这是对于一次操作带来的后果，如果是首位的话，只有一个相邻的会增加数值。
• 所以我们有一种想法是，将 $sort(b.begin(),b.end())$ 显然这样想法是错误的。例如当 $a[]=[2,6,7,3],b[]=[3,6,2,5]$ 。我的正确选法应该是 $1,4,3,2$。
• 由此可以看出我们只需要比较首尾 $b[i]$ 的大小即可，这样看来每个数值最多被增加一次，而且最大的 $b[i]$ 不会被使用，所以代码就非常简单。

#include
using namespace std;

int main()
{
    int T;cin>>T;
    while (T--)
    {
        int n;cin>>n;
        vector<int> a(n),b(n);
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        sort(b.begin(),b.end());
        long long res=0;
        for(int i=0;i<n;i++) res+=(a[i]+b[i]);
        cout<<res-b[n-1]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19