最大最小差
题目描述
现在有N个正整数，每一次去掉其中2个数a和b，然后加入一个数a*b+1，这样最后只剩下一个数p。要求求出最大的p记为maxp，最小的p记为minp，和他们的差K=maxp-minp。
编程任务：对于给定的数列，编程计算出它的max,min和K。
输入
输入（标准输入）：第一行是数列的长度N（不超过2000），以下N行，每行一个正整数（不超过9位）。
输出
输出（标准输出）：输出一共三行，每行一个整数，依次为max,min,K。
样例输入
2 1 1
样例输出
2 2 0
题解
高精度懒得写了
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; ll mn,mx,hp[2001]; int n,sz,a[2001]; void put(ll x,bool f)//f=1大根堆,f=0小根堆 { hp[++sz]=x; int now=sz; while(now>1) { if(f&&hp[now>>1]>=hp[now])break; if(!f&&hp[now>>1]<=hp[now])break; swap(hp[now],hp[now>>1]); now>>=1; } } ll get(int f) { ll t=hp[1];hp[1]=hp[sz--]; int next,now=1; while(now<=(sz>>1)) { next=(now<<1); if(next<sz) { if(f&&hp[next|1]>hp[next])next++; if(!f&&hp[next|1]<hp[next])next++; } if(f&&hp[next]<=hp[now])return t; if(!f&&hp[next]>=hp[now])return t; swap(hp[next],hp[now]); now=next; } return t; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int x,y; for(int i=1;i<=n;i++) put(a[i],0); for(int i=1;i<n;i++) { x=get(0);y=get(0); put(x*y+1,0); } mx=hp[1];sz=0; for(int i=1;i<=n;i++) put(a[i],1); for(int i=1;i<n;i++) { x=get(1);y=get(1); put(x*y+1,1); } mn=hp[1]; printf("%lld\n%lld\n%lld",mx,mn,mx-mn); return 0; } |
Subscribe
计数器 9787671
OI 课件=>
OI 课件=>