一本通 1.1 练习 1【数列极差】

求最大值先乘小的，最小值先乘大的。可以用堆来维护。

因为正常来说，每个数都是能被乘到的，但是它还有一个加一，所以将越多个加一乘到最大的上面就是最大值，因此应该先乘最小的数，以此类推。

最小值同理。

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, a[50010], ansMax, ansMin;
 5 priority_queue < int > Max;
 6 priority_queue < int, vector < int >, greater < int > > Min;
 7 int main()
 8 {
 9     scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), Max.push(a[i]), Min.push(a[i]);
10     while(!Max.empty())
11     {
12         if(Max.size() == 1) {ansMin = Max.top(); break;}
13         int x = Max.top(); Max.pop();
14         int y = Max.top(); Max.pop();
15         Max.push(x * y + 1);
16     }
17     while(!Min.empty())
18     {
19         if(Min.size() == 1) {ansMax = Min.top(); break;}
20         int x = Min.top(); Min.pop();
21         int y = Min.top(); Min.pop();
22         Min.push(x * y + 1);
23     }
24     printf("%d", ansMax - ansMin);
25     return 0;
26 }