1481 -- 【贪心练习】数列极差
Description 佳佳的老师在黑板上写了一个由n个正整数组成的数列,要求佳佳进行如下操作:每次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数为止,在所有按这种操作方式最后得到的数中,最大的为max,最小的为min, 则该数列的极差定义为M=max%mod-min%mod。
由于佳佳忙于准备期末考试,现请你帮助他,对于给定的数列,计算出相应的极差d。
Input
第一行为两个正整数n和mod,n分别表示正整数序列的长度(0≤n≤50000,mod≤10^9)
第二行为n个用空格隔开的正整数。
Output
输出文件只有一行为所求的极差M。
Sample Input
3 10007 1 2 3
Sample Output
2
我的代码
//hanyiyang c++ code
#include <bits/stdc++.h>
#define MAXN 50005
using namespace std;
unsigned long long n,mod;
unsigned long long num[MAXN];
priority_queue<long long,vector<long long>,less<long long> >big_q;
priority_queue<long long,vector<long long>,greater<long long> >little_q;
void init(){
scanf("%d %d",&n,&mod);
for(int i=1;i<=n;++i)
scanf("%d",&num[i]),big_q.push(num[i]),little_q.push(num[i]);
return;
}
void get_range(){
int n1,n2;
int maxn,minn;
while(big_q.size()!=1) {
n1=big_q.top();
big_q.pop();
n2=big_q.top();
big_q.pop();
big_q.push((n1*n2+1)%mod);
}
minn=big_q.top();
minn=minn%mod;
while(little_q.size()!=1){
n1=little_q.top();
little_q.pop();
n2=little_q.top();
little_q.pop();
little_q.push((n1*n2+1)%mod);
}
maxn=little_q.top();
maxn=maxn%mod;
printf("%d",maxn-minn);
return;
}
int main(){
init();
get_range();
return 0;
}
此题用优先队列不行?40分!大佬求助