蓝桥杯[OJ 3791]—珠宝的最大交替和—CPP-贪心

一：问题描述

二、整体思路：

1. 观察到可以把交替和中各项分为奇数组与偶数组，最多只能交换一次，先假设要交换。
2. 偶数组的项都要减去，奇数组的项都要加上，交替和=奇数组总和-偶数组总和，那么如果交换的两项都同时位于奇数组或偶数组内，不能使得交替和最大。因此交换的两项必须一个位于偶数组，另一个位于奇数组。

3. 交换之后，ans_exchanged=ans_init+2*(被交换偶数-被交换奇数)

4. 因此，遍历偶数组，得到其减去奇数组中最小项的差，找出最大的差

5. 注意是差最大而不是最大的偶数项减去最小的奇数项

6. 注意最后要和不交唤的情况进行比较判断

三、代码：

#include
using namespace std;
using ll = long long;
const int n=1e6+10;
int arr[n];
vector<int> arr_double;
vector<int> arr_single;
int main(){
  int N;cin>>N;
  bool flag=true;
  ll ans_init=0;
  for(int i=1;i<=N;i++){
    cin>>arr[i];arr[i]=abs(arr[i]);//交替和各项都为绝对值
    if(flag){
      ans_init+=arr[i];
      arr_single.push_back(arr[i]);//奇数组
      flag=false;
    }else{
      ans_init-=arr[i];
      arr_double.push_back(arr[i]);//偶数组
      flag=true;
    }
  }
  sort(begin(arr_single),end(arr_single));
  //奇数和-偶数和，把小的奇数与比它大的偶数交换,交换之后ans_exchanged=ans_init+2*(偶数-奇数)，找到最大的ans_exchanged
  ll subtract_max=LLONG_MIN;
  for(auto i:arr_double){
    if(i-arr_single[0] > subtract_max) subtract_max=i-arr_single[0];
  }
  cout<<max(ans_init+2*subtract_max,ans_init);//不要忘记和不交换的情况比较
  return 0;
}