P9852 [ICPC2021 Nanjing R] Windblume Festival 题解

wylnh · 2023-11-16 22:44:04 · 题解

做法：模拟

题意：一个长为 n 的环形数组，每次操作对于任意 i,j，删除 a_j，将 a_i 减去 a_j，使得最后剩余的数最大。

思路：由题意可知，一次操作即将两数合并为两数之差。因此假设按操作先后顺序， a_1 表示最后一个操作的数， a_n 表示第一个操作的数，题意即为将 a_1 到 a_n 连成一个算式，在每个数之前添加一个符号，使得算式值最大。

• 对于第 i 个数，若想让其符号为 +，则需将其与第 i-1 个数做一次操作，否则直接操作。
• 比如想构造 a_1-a_2-a_3+a_4+a_5，则：
  • 先从前往后找第一个符号为 + 的数，即 a_4，那么就将其与 a_3 做一次操作，得到 a_1,a_2,a_3-a_4,a_5。
  • 同样找到符号为 + 的 a_5，将其与 a_3-a_4 做一次操作，得到 a_1,a_2,a_3-a_4-a_5。
  • 最后剩下的都是 - 号了，就直接依次进行操作，得到 a_1-a_2-(a_3-a_4-a_5)，即 a_1-a_2-a_3+a_4+a_5。
• 所以只需要选择相邻的数，前一个为 + 号，后一个为 - 号，两两做差，枚举最大值即可。
• 注意：当 n=1 时，直接输出 a_1，无需进行操作。

代码：

#include<bits/stdc++.h>
#define ll long long
#define INF -0x7f7f7f7f
using namespace std;
const int N=1e6+10;
ll T,n,a[N];
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        ll sum=0,ans=INF;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=abs(a[i]);//统计最大可能达到的值
        }
        if(n==1){//特判
            cout<<a[1]<<"\n";
            continue;
        }
        for(int i=1;i<=n;i++){
            ans=max(ans,sum-abs(a[i])-abs(a[i%n+1])+a[i]-a[i%n+1]);//sum减去两数的绝对值，加上做差后的值，即为每次操作的贡献
        }
        cout<<ans<<"\n";
    }

    return 0;
}

后记：如有错误或不足请 dalao 指出。（点个再走呀！）