习题加餐 4.珠宝的最大交替和

标签：int 元素交换算法 long 交替加餐习题珠宝

问题描述
小莉是一位珠宝设计师，她非常喜欢玩珠子。她有一个长度为N的珠串A,每个珠子有不同的颜色和大小，她想要用这个珠串来设计一款新的珠宝。
她将该珠串的交替和定义为：
S=|A₁|-|A₂|+|A₃|-|A₄|+……+(-1)*-1.|Avl小莉可以进行以下操作，但最多只能进行一次：
选择两个位置i和j(1≤i<j≤N),交换A₁和Aj。
为了让新的珠宝更加漂亮，小莉想要让交替和最大。请你帮她找出最大的交替和。其中，|X|表示珠子X的大小的绝对值。
输入格式
第一行包含一个整数N,表示珠串A的长度。
第二行包含N个用空格分隔的整数，表示珠串A中每个珠子的大小。数据范围保证：1≤N≤10⁵,-10⁹≤A;≤10°。
输出格式
输出一行，表示小莉最多可以通过进行操作获得的最大交替和。
样例输入
7
-3 -2 -10123
样例输出
6
说明
对于样例，最优的交换方案是选择i=2和j=3,将-2和-1换位置，得
到数组[-3,-1,-2,0,1,2,3],此时交替和为|-3|-|-1|+|-2|-
|0|+|1|-|2|+|3|=6。
运行限制
语言
最大运行时间
最大运行内存
C++
2s
256M
C
2s
256M
Java
3s
256M
Python3
4s
256M
PyPy3
4s
256M
Go
4s
256M
JavaScript
4s
256M

我的答案：(15个样例14个都是错的或者超时的)

一、信息

珠串长度：N
珠子大小数组：A，长度为N，每个元素代表珠子的大小。
操作：最多交换一次两个位置i和j的珠子，以使得交替和S最大。
交替和：S = |A₁| - |A₂| + |A₃| - |A₄| + … + (-1)^(N-1)|AN|。

二、分析

信息的作用：
- 珠串长度N决定了遍历和计算的范围。
- 珠子大小数组A提供了计算交替和的基础数据。
- 操作限制（最多交换一次）对我们设计算法时的策略有重要影响。
思考和分析过程：
- 初始交替和的计算：首先计算未经交换的珠串的交替和。
- 最优交换策略：通过分析，我们发现最优交换应该发生在使得交替和增幅最大的两个珠子之间。
- 如何找到这两个珠子：考虑到交替和的性质，我们需要找到一对珠子，其一在偶数位置（实际增加交替和），另一个在奇数位置（实际减少交替和），且这种交换能最大程度地增加交替和。
分析过程：
- 分别计算偶数位置和奇数位置珠子对交替和的贡献。
- 遍历珠串，尝试每一对可能的交换，并计算其对交替和的潜在影响。
- 记录潜在增加最大的交换方案。

三、算法设计

初始交替和计算：遍历一遍数组，根据位置是奇数还是偶数，计算未交换珠串的初始交替和。
最大交替和计算：
- 遍历数组，对于每个元素，考虑将其与其他所有元素交换后的交替和变化。
- 考虑到交换两个元素，实际上是改变了这两个元素的正负贡献，因此我们需要计算交换任意两个元素后的交替和变化。
- 跟踪并更新可能的最大交替和。
边界条件处理：确保i和j的选择在数组范围内且满足1≤i<j≤N。

四、代码实现

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long maxAlternateSum(vector<int>& A) {
    long long initialSum = 0;
    int N = A.size();

    // 计算未交换的初始交替和
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) initialSum += abs(A[i]);
        else initialSum -= abs(A[i]);
    }

    long long maxSum = initialSum;
    // 尝试交换每对元素并更新最大交替和
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            long long newSum = initialSum;
            // 如果i和j一个是奇数位置一个是偶数位置，则交换后交替和会变化
            if ((i % 2) != (j % 2)) {
                if (i % 2 == 0) {
                    newSum = newSum - abs(A[i]) + abs(A[j]) + abs(A[i]) - abs(A[j]);
                } else {
                    newSum = newSum + abs(A[i]) - abs(A[j]) - abs(A[i]) + abs(A[j]);
                }
            }
            maxSum = max(maxSum, newSum);
        }
    }

    return maxSum;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    cout << maxAlternateSum(A) << endl;

    return 0;
}

五、可能遇到的问题

性能问题：对于每对元素的交换尝试，我们的算法复杂度接近O(N^2)，在N非常大时可能会导致时间超限。
溢出问题：由于珠子的大小范围和N的范围，计算过程中可能会遇到整数溢出的问题，特别是在使用int类型时。可以通过使用long long类型来缓解这个问题。
逻辑错误：在计算交替和变化时，可能会出现逻辑判断错误，特别是在处理奇偶位置和交替和变化计算时。
数组下标越界：在遍历和交换元素时，需要仔细处理边界条件，避免数组下标越界。

#include<bit5s/stdc++.h>
using namespace std;
typedef long long ll;
int maxAdd(ll a[i]){
  
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int N;
  cin>>N;
  vector<ll> Ai(N);
  for(int i=0;i<N;i++){
    cin>>Ai(i);
  }
}

官方答案：

解题思路：

不熟悉贪心算法的读者可以看看我的这篇博客：2.9 蓝桥杯基础算法之贪心算法

源代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define all(s) s.begin(),s.end()

int n;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    std::vector<int> a, b;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        x = abs(x);
        if (i % 2) b.push_back(x);
        else a.push_back(x);
    }
    if (n == 1) {
        cout << abs(a[0]) << '\n';
        return 0;
    }
    int mi = *min_element(all(a));
    int mx = *max_element(all(b));
    LL ans = accumulate(all(a), 0LL) - accumulate(all(b), 0LL);
    if (mx >= mi)ans += 2 * mx - 2 * mi;
    cout << ans << '\n';
    return 0;
}

我对答案的理解：

如果你还是不理解贪心算法可以看看我这篇博客：4-2 贪心算法的基本要素

初始理解

交替和是由位于偶数位置的元素的和减去位于奇数位置的元素的和得到的。我们可以定义两个变量：

Se（偶数和）为所有偶数位置（索引为0, 2, 4, ...）的元素之和。
So（奇数和）为所有奇数位置（索引为1, 3, 5, ...）的元素之和。

解题思路

为了最大化最终的交替和，我们需要最大化Se并最小化So。只允许进行一次操作，即交换一个偶数位置的元素与一个奇数位置的元素。

根据提供的证明和算法，我们可以得知：

如果两个交换的元素同为奇数或偶数，那么它们对交替和没有影响。
如果我们要交换，应该交换最小的偶数位置上的元素（减少Se）和最大的奇数位置上的元素（减少So）。

代码解释

接下来是提供的C++代码，我将逐行进行解释：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define all(s) s.begin(),s.end()

int n;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    std::vector<int> a, b;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        x = abs(x);  // 取绝对值，因为元素大小的贡献是绝对值
        if (i % 2) b.push_back(x);  // 如果是奇数位置，加入b
        else a.push_back(x);  // 如果是偶数位置，加入a
    }
    if (n == 1) {
        cout << abs(a[0]) << '\n';  // 如果只有一个元素，交替和就是该元素的绝对值
        return 0;
    }
    int mi = *min_element(all(a));  // 在偶数位置找最小元素
    int mx = *max_element(all(b));  // 在奇数位置找最大元素
    LL ans = accumulate(all(a), 0LL) - accumulate(all(b), 0LL);  // 计算原始交替和
    if (mx >= mi) ans += 2 * (mx - mi);  // 如果可以交换，则加上交换带来的增量
    cout << ans << '\n';  // 输出最终的交替和
    return 0;
}

解释如下：

#include<bits/stdc++.h>：这个头文件包含了大多数标准库的头文件，使得在竞赛编程中快速编写代码成为可能。
typedef long long LL;：为了处理大数，我们用 long long 类型来定义整数。
vector<int> a, b;：我们创建两个数组 a 和 b，分别用来存储偶数位置和奇数位置上的元素的绝对值。
min_element 和 max_element 函数分别用来找出a中的最小元素和b中的最大元素。
accumulate 函数用来计算所有偶数位置元素之和和所有奇数位置元素之和，进而得到原始的交替和 Se - So。
最后，如果最大的奇数位置元素大于等于最小的偶数位置元素，则交替和可以通过执行一次交换操作来增加2 * (mx - mi)。

时间复杂度

整个算法的时间复杂度是O(n)，因为每一个步骤（寻找最小元素、最大元素、求和）都可以在线性时间内完成。

通过这种方法，我们不需要检查每对可能的交换位置，因此算法非常高效，适合处理大量数据的情况。

六、不足(不完美的地方)

正确答案已经非常高效且精准地解决了问题，运行时间为 �(�)O(N)，这是非常适合处理高达 105105 数量级输入的。然而，总有一些方面是可以进行改进的：

代码可读性：使用了 #include<bits/stdc++.h> 和 using namespace std 这种做法在工业级代码中通常是不推荐的。因为 bits/stdc++.h 是一个GCC特有的编译器特定的头文件，它可能在其他编译器上不可用，并且它会包含许多不必要的头文件，可能会增加编译时间。通常，最好只包含程序实际用到的标准库头文件。
宏定义：#define all(s) s.begin(),s.end() 宏定义虽然简化了代码，但在大型项目中，它们可能会导致可读性问题和调试难度，因为宏不提供类型安全，并且可能会在不同上下文中产生意外的行为。使用函数或者模板是更加现代且安全的C++实践。
错误处理：代码中没有对输入错误或异常值进行处理，例如输入的不是整数。在实际的软件工程实践中，健壮的错误处理是很重要的。
单一职责：main 函数负责了多个任务：处理输入、算法逻辑和输出结果。在更复杂的系统中，我们可能希望将这些分离开来，将算法逻辑放在单独的函数或者类中，这样有助于测试和重用代码。
变量命名：变量 a, b, mi, mx 和 ans 等名称虽然在算法竞赛中常见，但在商业代码中，更具描述性的变量名可以提高代码的可读性和可维护性。
模块化：将计算交替和的逻辑封装到一个单独的函数中，这样可以提高代码的模块化程度，也便于单独测试和复用。
算法优化：尽管当前算法已经很有效，但如果输入数据有特定的模式或者分布，可能还可以进一步优化。例如，如果我们知道珠子大小是随机分布的，那么可能在某些情况下可以提前终止搜索。
内存使用：当前算法创建了两个额外的数组 a 和 b 来存储奇偶位置上的值，这在空间复杂度上是可优化的。如果原始数组不需要保留，我们可以直接在原数组上操作，或者仅仅使用几个变量来追踪所需的最大和最小值。

这些改进点是从不同的角度提出的，其中一些是为了提高代码质量和可维护性，而有些则是为了在特定情境下提高性能。在竞赛编程中，一些实践（如使用宏和 bits/stdc++.h）是为了快速编写和提交解决方案，但在生产环境中，则更倾向于清晰和可维护的代码。

七、疑问

问题1：为什么我的答案错了？

错误原因如下：

算法效率：原始的方法尝试所有可能的交换，这在数据量大的情况下会导致时间超时，因为每增加一个元素，就会增加几乎 N 次的额外计算。
未充分利用问题性质：题目中的目标是最大化交替和，我的原始方法没有充分利用问题的性质，即通过一个贪心的策略找到最优解。最优解只需要一次交换就可以实现，这是通过比较偶数位置的最小值和奇数位置的最大值来完成的。
过度复杂的解法：没有必要检查每一对可能的交换，因为只有奇偶位置的交换才会影响最终结果，而且交换的目的是要么增加正数的总和，要么减少负数的总和，不需要详尽的两两比较。

正确的解决方案识别出了这样一个事实：通过找到偶数索引中的最小值和奇数索引中的最大值，我们可以通过一次交换就实现交替和的最大化，因为这样的交换会给出最大的正数和最小的负数贡献差值。这一点可以通过一个简单的 O(N) 时间复杂度的遍历来实现，然后根据需要执行最多一次的交换来调整交替和。通过这种方法，我们可以确保算法既高效又准确。

八、总结

心算法的应用：
- 贪心算法通常用于求解最优化问题。这个问题展示了如何通过每一步都做出局部最优选择（即最大化偶数位置上的元素和最小化奇数位置上的元素）来获得全局最优解。
问题简化：
- 这个问题可以通过简化交替和的计算来高效解决。而不是考虑所有可能的交换，只需找到关键的影响因素（即偶数位置的最小值和奇数位置的最大值）。
算法效率的重要性：
- 高效的算法可以处理大量数据。这道题展示了如何将一个看似复杂的问题（需要比较所有可能的交换）转换为线性时间复杂度的问题。
数组处理技巧：
- 学习如何使用C++标准库中的函数（例如std::min_element, std::max_element, std::accumulate）来简化数组处理。
数学知识的应用：
- 理解和应用数学知识（如绝对值和奇偶性）来设计算法和解决问题。
代码编写实践：
- 这个问题也教会了如何编写简洁而高效的代码，这在算法竞赛中是非常重要的，但在实际软件开发中，可能需要更加关注代码的可读性和维护性。
边界情况考虑：
- 在实际问题中，考虑边界情况（如只有一个珠子的情况）是非常重要的，这可以确保算法的健壮性。
绝对值的运用：
- 在处理正负数问题时，绝对值的运用是一种常见的技巧，特别是在涉及距离或差异最大化时。
奇偶性分析：
- 这道题目强调了奇偶性分析的重要性，在许多数学和计算问题中，通过奇偶性来分类和简化问题是一个常用的技巧。
代码优化的考虑：
- 如何在保持算法正确性的同时减少内存使用和提高代码执行效率。

通过这道题目，可以学习到这些关键概念，它们不仅仅适用于解决特定问题，而且在计算机科学和编程的许多其他领域也非常有用。

标签：int,元素,交换,算法,long,交替,加餐,习题,珠宝
From： https://blog.csdn.net/tang7mj/article/details/136654949