【JZOJ】數列極差問題

JZOJ題目友鍊

題目描述

在黑闆上寫了 N N N個正整數組成的一個數列，進行如下操作： 每次擦去其中的兩個數 a a a和 b b b，然後在數列中加入一個數 a × b ＋ 1 a×b＋1 a×b＋1，如此下去直至黑闆上 剩下一個數，在所有按這種操作方式最後得到的數中，最大的為 m a x max max，最小的為 m i n min min， 則該數列的極差定義為 M ＝ m a x － m i n M＝max－min M＝max－min。

請你程式設計，對于給定的數列，計算極差 m m m。

輸入

第一行是數列的長度 n n n（不超過 10 10 10），第二行起是數列中 n n n個數，相鄰 2 2 2個數由空格分開;

每個數均不超過 100 100 100.

輸出

輸出一個整數表示數列極差m

樣例輸入

3
1  2  3
           

樣例輸出

2
           

分析：這道題拿到手呢，可以馬上看出來，這是用排序+模拟來做的。先把所有數排個序，然後做加減法就好了，就是這麼簡單！

Code：

#include<bits/stdc++.h>//Van♂能頭
using namespace std;
int s[10001],j[10001];//數組可以開大一點，防止RE
int cmp(int a,int b){//自定義函數，用來做sort函數時從大到小排序
	return a>b;
}
int main(){
	int n;
	cin>>n;
	for(register int i=0;i<n;++i){//輸入，不多說
		cin>>s[i];
		j[i]=s[i];//用另外一個數組再存一下這組數
	}
	sort(s,s+n);//從小到大排序
	for(register int i=1;i<n;++i){
		s[i]=s[i]*s[i-1]+1;//根據題意：數列中加入一個數a×b＋1
		sort(s+i,s+n);//再次排序
	}
	int max=s[n-1];//标記最大數
	sort(j,j+n,cmp);
	for(register int i=1;i<n;++i) j[i]=j[i-1]*j[i]+1;//同上
	int min=j[n-1];//此處時最小數
	cout<<max-min<<endl;//極差
	return EXIT_SUCCESS;//Van♂美結束
}
           

嗯這篇blog就到這裡了，樓下隐形字，歡迎掃一掃檢視↓。。。

我這麼蔡，不點贊，關個注鼓勵一下再走嗎？