\(根据贪心的策略，取max的时候尽量保证数列中两个最小的数相乘，取min反之\)
\(用优先队列维护数列，复杂度O(nlogn)\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<stdio.h> #include<algorithm> #include<queue> using namespace std; priority_queue<int> a; priority_queue<int, vector<int>, greater<int> > b; int n; int main() { scanf("%d", &n); for (int i = 1, x; i <= n; ++i) { scanf("%d", &x); a.push(x); b.push(x); } while(a.size() > 1) { int x = a.top(); a.pop(); int y = a.top(); a.pop(); a.push(x*y+1); x = b.top(); b.pop(); y = b.top(); b.pop(); b.push(x*y+1); } printf("%d", b.top()-a.top()); return 0; } |