数列极差问题

题目内容

题目OJ地址：http://acm.hit.edu.cn/problemset/1062

在黑板上写N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个数$a$和$b$，然后在数列中加入$a \times b + 1$，如此下去直至黑板上剩下一个数字，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M = max - min。请编程计算出给定数列的极差。

---

思路

  对于这个问题，最基本的思路就是分别计算出min和max，最后求差即可。那么现在问题就转换为如何去求min和max。根据题目可以知道，计算的过程实质上就是用一个数去代替两个数的过程，所以算法的关键在于每一步我们怎么去选出两个数。

  可能到这里仍然没有思路，我们可以先从结果倒推。如果我们想求得一个比较大的结果，那么$a$和$b$两个数都应该是比较大的。如果一个很小，一个很大，最终的结果也会比较小（例如，1*10 + 1 小于 4 * 5 + 1）。这样一来，我们可以优先考虑使用贪心的策略。每一次我们找最小的两个数，这样就能使数组中的数字都尽可能地大。这样可保证的是每一轮操作结束后，数组中的元素是所有操作中能获得的最大的元素。因此也就保证了最后一步我们能得到最大的结果max。

  mind的求解同理，但是可能有点不太好理解。有人会问，每次挑选最大的两个元素，那么得出来的东西不是更大吗？怎么能求到最小值？但是别忘了，因为数组中剩下的元素都是比较小的，尤其是最后一次操作中，剩下的两个元素有一个是数组中最小的元素，这个元素能够中和掉很大的元素，从而得出一个较小的值。

---

实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  while (1) {
    int n;
    cin >> n;

    if (n == 0) {
      return 0;
    }
    vector<int> v1;
    vector<int> v2;
    while (n--) {
      int tmp;
      cin >> tmp;
      v1.push_back(tmp);
      v2.push_back(tmp);
    }

    // Find min
    // 从小到大
    // sort(v1.begin(), v1.end());
    // cout << v1[0] << endl;
    while (v1.size() != 1) {
      sort(v1.begin(), v1.end()); // 可省略
      int a = v1[v1.size() - 1];
      int b = v1[v1.size() - 2];
      int tmp = a * b + 1;
      v1.pop_back();
      v1.pop_back();
      v1.push_back(tmp);
    }
    // cout << "Min: " << v1[0] << endl;
    // Find max
    // 从大到小
    // sort(v2.rbegin(), v2.rend());
    // cout << v2[0] << endl;
    while (v2.size() != 1) {
      sort(v2.rbegin(), v2.rend());
      int a = v2[v2.size() - 1];
      int b = v2[v2.size() - 2];
      int tmp = a * b + 1;
      v2.pop_back();
      v2.pop_back();
      v2.push_back(tmp);
    }
    // cout << "Max: " << v2[0] << endl;
    cout << v2[0] - v1[0] << endl;
  }
  return 0;
}

这里为了vector操作的方便，我都是在尾部进行删除和插入操作，注意排序的不同（begin()和rbegin()）。同时，在计算min的时候，因为我们删除掉两个大的，在最后插入一个更大的数，所以是不需要重复排序的。

---

总结

  这道题是贪心算法的一个应用。思考起来有点困难，但是想到了方法实际操作就很简单，所以大家在碰到求极值的时候不妨考虑一下贪心算法。希望这篇博客能够帮助到你，谢谢！