貪心。關(guān)鍵是證明子問題最優(yōu)即是總問題最優(yōu)。

可以考慮三個(gè)數(shù)的情況，易證選取最小的數(shù)擦除將得到最大數(shù)，vice versa 。故總體也是如此。

用優(yōu)先隊(duì)列實(shí)現(xiàn)。STL自帶仿函數(shù)greater<>用于調(diào)整小頂堆。

#include

#include

using namespace std;

int main()

{

int n;

while(scanf("%d",&n)&&n)

{

int a[50005];

priority_queue q;

while(!q.empty()) q.pop();

for(int i=0;i

{

scanf("%d",&a[i]);

q.push(a[i]);

}

for(int i=0;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,greater > pq;

while(!pq.empty()) pq.pop();

for(int i=0;i

for(int i=0;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;

}

總結(jié)

以上是生活随笔為你收集整理的java的数列极差_[hoj]数列极差问题 | 学步园的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。