贪心。关键是证明子问题最优即是总问题最优。
可以考虑三个数的情况,易证选取最小的数擦除将得到最大数,vice versa 。故总体也是如此。
用优先队列实现。STL自带仿函数greater<>用于调整小顶堆。
#include <cstdio> #include <queue> using namespace std; int main() { int n; while(scanf("%d",&n)&&n) { int a[50005]; priority_queue<int> q; while(!q.empty()) q.pop(); for(int i=0;i<n;i++) { scanf("%d",&a[i]); q.push(a[i]); } for(int i=0;i<n-1;i++) { int x = q.top(); q.pop(); int y = q.top(); q.pop(); q.push(x*y+1); } int min = q.top(); q.pop(); priority_queue<int,vector<int>,greater<int> > pq; while(!pq.empty()) pq.pop(); for(int i=0;i<n;i++) pq.push(a[i]); for(int i=0;i<n-1;i++) { int x = pq.top(); pq.pop(); int y = pq.top(); pq.pop(); pq.push(x*y+1); } int max = pq.top(); pq.pop(); printf("%d\n",max-min); } return 0; }