ZOJ 3447 Doraemon's Number Game（优先队列+高精度运算）

落日映苍穹つ 2022-06-10 05:17 75阅读 0赞

Doraemon and Nobita are playing a number game. First, Doraemon will give Nobita *N*positive numbers. Then Nobita can deal with these numbers for two rounds. Every time Nobita can delete *i* (2 ≤ *i* ≤ *K*) numbers from the number set. Assume that the numbers deleted is a\[ 1 \], a\[ 2 \] ... a\[ i \]. There should be a new number *X* = ( a\[ 1 \] \* a\[ 2 \] \* ... \* a\[ i \] + 1 ) to be inserted back into the number set. The operation will be applied to the number set over and over until there remains only one number in the set. The number is the result of round. Assume two results *A* and *B*are produced after two rounds. Nobita can get |*A* \- *B*| scores.

Now Nobita wants to get the highest score. Please help him.

Input

Input will contain no more than 10 cases. The first line of each case contains two positive integers *N* and *K* (1 ≤ *N* ≤ 100, 1 ≤ *K* ≤ 50). The following line contains *N* positive integers no larger than 50, indicating the numbers given by Doraemon.

<h4< dd="">

Output

For each case, you should output highest score in one line.

<h4< dd="">

Sample Input

6 3
    1 3 4 10 7 15

<h4< dd="">

Sample Output

5563

<h4< dd="">

Hint

For most cases, *N* ≤ 20

题解：

题意：

给n个数，有两轮操作，每轮操作你可以选择大于2小于k个数字进行题目说的运算，让你求两轮差值最大为多少

思路：

每次取k个最大的数字合并为最小的值

每次取2个最小的数字合并为最大值

比赛的时候思路和题解思路一模一样。。比赛的时候wa了，也考虑过longlong会炸的情况，但是高精度写起来太麻烦了，所以就放弃了，刚刚搜了个高精度模板。。。卧槽还有这种操作，加上高精度模板这题瞬间就ac了。。感觉捡到一个宝hhhhh

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    #define INF 100861111;
    using namespace std;
    class bigInt//大数运算模板
    {
    public:
        int num[302],len;
        bigInt() {num[0]=0,len=0;}
        bigInt operator=(const int &a)
        {
            int tmp=a;
            len=0;
            while(tmp)
                num[len++]=tmp%10,tmp/=10;
            if (!len)num[0]=0,len=1;
        }
        bigInt(const int &a)
        {
            int tmp=a;
            len=0;
            while(tmp)
                num[len++]=tmp%10,tmp/=10;
            if (!len)num[0]=0,len= 1;
        }
        friend bool operator<(const bigInt &b,const bigInt &a)
        {
            if (a.len!=b.len)
                return b.len<a.len;
            for (int i=b.len-1;i>=0;i--)
                if (b.num[i]!=a.num[i])
                    return b.num[i]<a.num[i];
            return false;
        }
        friend bool operator>(const bigInt & b,const bigInt &a)
        {
            if (a.len!=b.len)
                return b.len>a.len;
            for (int i=b.len-1;i>=0;i--)
                if (b.num[i]!=a.num[i])
                    return b.num[i]>a.num[i];
            return false;
        }
        bigInt operator+(const bigInt &a)
        {
            bigInt res;
            int i,j,c =0,adda,addb;
            for (i=0,j=0;i<len||j<a.len||c;)
            {
                adda=0,addb=0;
                if(i <len)
                    adda= num[i++];
                if(j< a.len)
                    addb=a.num[j++];
                res.num[res.len++]=(adda+addb+c)%10;
                c=(adda+addb+c)/10;
            }
            return res;
        }
        bigInt operator-(const bigInt &b)
        {
            bigInt res;
            int i,j,c=0,suba,subb;
            for(i=0,j=0;i<len||j<b.len||c;)
            {
                suba=0,subb=0;
                if(i<len)
                    suba=num[i++];
                if(j<b.len)
                    subb=b.num[j++];
                res.num[res.len++] =(suba-subb+c+10)%10;
                c=(suba-subb+c+10)/10-1;
            }
            for(i=res.len-1;i>0;i--)
                if (res.num[i])break;
            res.len=i+1;
            return res;
        }
        bigInt operator*(const bigInt &b)
        {
            bigInt res;
            int i,j,c,now,mulb,tmp;
            memset(res.num,0,sizeof(int)*(len+b.len));
            for(i=0;i<len;i++)
            {
                now=i,c=0;
                for(j=0;j<b.len||c;)
                {
                    mulb=0;
                    if (j<b.len)
                        mulb=b.num[j++];
                    tmp=res.num[now]+num[i]*mulb+c;
                    res.num[now++]=tmp % 10;
                    c=tmp/10;
                }
            }
            for(i=len+b.len-1;i>0;i--)
                if (res.num[i]) break;
            res.len = i + 1;
            return res;
        }
        void display()
        {
            int i;
            for (i=len-1;i>1;i--)
                if (num[i])break;
            for (;i>=0;i--)
                printf("%d",num[i]);
            printf("\n");
        }
    };
    priority_queue<bigInt,vector<bigInt>,less<bigInt> >q1;//最大堆
    priority_queue<bigInt,vector<bigInt>,greater<bigInt> >q2;//最小堆
    int main()
    {
        int i,j,n,k,x;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            while(!q1.empty())
                q1.pop();
            while(!q2.empty())
                q2.pop();
            for(i=0;i<n;i++)
            {
                scanf("%d",&x);
                bigInt t=x;
                q1.push(t);
                q2.push(t);
            }
            while(q1.size()>1)//最小值情况
            {
                if(q1.size()>=k)
                {
                    bigInt t=1;
                    for(i=0;i<k;i++)
                    {
                        t=t*q1.top();
                        q1.pop();
                    }
                    t=t+1;
                    q1.push(t);
                }
                else
                {
                    bigInt t=1;
                    while(!q1.empty())
                    {
                        t=t*q1.top();
                        q1.pop();
                    }
                    t=t+1;
                    q1.push(t);
                    break;
                }
            }
            while(q2.size()>1)//最大值情况
            {
                bigInt t=1;
                for(i=0;i<2;i++)
                {
                    t=t*q2.top();
                    q2.pop();
                }
                t=t+1;
                q2.push(t);
            }
            bigInt t1=q2.top();
            bigInt t2=q1.top();
            bigInt temp=t1-t2;//差
            temp.display();
        }
        return 0;
    }