蓝桥杯备考冲刺必刷题（C++） | 3791 珠宝的最大交替和

学习C++从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（C++） | 汇总-CSDN博客

【题目描述】
小莉是一位珠宝设计师，她非常喜欢玩珠子。她有一个长度为 N N N的珠串 A A A，每个珠子有不同的颜色和大小，她想要用这个珠串来设计一款新的珠宝。
她将该珠串的交替和定义为：
S = ∣ A 1 ∣ − ∣ A 2 ∣ + ∣ A 3 ∣ − ∣ A 4 ∣ + ⋯ + ( − 1 ) N − 1 ⋅ ∣ A N ∣ S = |A_1|-|A_2|+|A_3|-|A_4|+\dots + (-1)^{N-1}\cdot |A_N| S=∣A1​∣−∣A2​∣+∣A3​∣−∣A4​∣+⋯+(−1)N−1⋅∣AN​∣
小莉可以进行以下操作，但最多只能进行一次：
选择两个位置 i i i和 j ( 1 ≤ i < j ≤ N ) j(1\le i\lt j\le N) j(1≤i<j≤N)，交换 A i A_i Ai​和 A j A_j Aj​。
为了让新的珠宝更加漂亮，小莉想要让交替和最大。请你帮她找出最大的交替和。
其中， ∣ X ∣ |X| ∣X∣表示珠子X的大小的绝对值。
【输入】
第一行包含一个整数 N N N，表示珠串 A A A的长度。
第二行包含 N N N个用空格分隔的整数，表示珠串 A A A中每个珠子的大小。
【输出】
输出一行，表示小莉最多可以通过进行操作获得的最大交替和。
【输入样例】

7
-3 -2 -1 0 1 2 3

【输出样例】

6

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int odd[100005], even[100005], ans;
bool cmp(int x, int y)
{
    return x>y;
}
signed main()
{
    cin >> n;
    int cur1=0, cur2=0;  // 定义奇数数组和偶数数组的下标
    for (int i=1; i<=n; i++) {
        int t;
        cin >> t;
        if (i%2==1) {  // 是奇数就放到奇数数组中
            odd[++cur1] = abs(t);
            ans += abs(t);
        } else {  // 是偶数就加到偶数数组中
            even[++cur2] = abs(t);
            ans -= abs(t);
        }
    }
    if (n==1) {  // 如果只有1个珠子的情况
        cout << odd[1] << endl;
        return 0;
    }
    sort(even+1, even+cur2+1, cmp);  // 取出偶数数组的最大值
    sort(odd+1, odd+cur1+1);  // 取出奇数数组的最小值
    if (even[1]>odd[1]) {  // 只有当偶数大于奇数时，才操作
       ans = ans - odd[1] + even[1] + even[1] - odd[1];
    }
    cout << ans << endl;
    return 0;
}

【运行结果】

7
-3 -2 -1 0 1 2 3
6