「一本通 1.1 练习 1」数列极差-白红宇

「一本通 1.1 练习 1」数列极差

阅读量：6913 次

发布时间：2019-06-27

本文共 1073 字，大约阅读时间需要 3 分钟。

解题思路

这题也是典型的贪心算法题。

对于这个问题先通过实例来认识问题所描述的计算过程。

令$ N=3 $ ,取数列 $ 3,5,7 $

可能有下面三种情况

$ (3×5+1)×7+1=113 $

$ (3×7+1)×5+1=111 $

$ (5×7+1)×3+1=109 $

由此可见先运算小数据的到的是最大值,先运算大数据得到的是最小值。

故针对此问题可采用贪心算法，下面验证其合理性：

不妨假设 $ 3 $ 个数 $ a<b<c $ 。

则有以下几种组合计算结果:

$ 1.(a×b+1)×c+1= abc + c + 1 $

$ 2.(a×c+1)×b+1= abc + b + 1 $

$ 3.(b×c+1)×a+1= abd + a + 1 $

显然，选择两个较小数能得到最大的结果，而选择两个较大的数能得到最小的结果，上述算法的正确性得证。推广至n个数，该算法的单调性也显而易见。

#include 
    
     #define _for(i,a,n) for(int i=a;i
     
      >t;while(t--)#define close() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;typedef long long ll;typedef pair
      
        P;const int maxn = 5e4;priority_queue

, greater

> Q1;priority_queue

, less

> Q2;int main(){ int n, t; cin >> n; _for(i, 0, n) { cin >> t; Q1.push(t); Q2.push(t); } cin >> t; int maxv = 0, minv = 0; while(Q1.size() != 1) { t = Q1.top(); Q1.pop(); t = t * Q1.top() + 1; Q1.pop(); Q1.push(t); t = Q2.top(); Q2.pop(); t = t * Q2.top() + 1; Q2.pop(); Q2.push(t); } cout << Q1.top() - Q2.top() << endl; return 0;}

转载于:https://www.cnblogs.com/mbath/p/10172151.html