2018ICPC青岛赛区J题

题目链接：http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1

这题真的坑，为什么要买0本书的时候，书架里面刚好有价格为0的时候输出“Richman”，难道不应该是“Impossible”吗？？你肯定是要从头开始来一遍的，我觉得应该是不可能，，被这个题给卡住了。。。

AC代码;

#include<iostream>

#include<string>

#include<cstring>

#include<iomanip>

#include<cmath>

#include<algorithm>

#include<stdio.h>

#include<queue>

#include<stack>

#include<vector>

using namespace std;

# define inf 0x3f3f3f3f

# define maxn 500000+100

# define ll long long

int a[maxn];

int b[maxn];

ll Min(ll t1,ll t2)

{

    return t1>t2?t2:t1;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        int num=0;

        scanf("%d%d",&n,&m);

        for(int i=1; i<=n; i++)

        {

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

            if(a[i]!=0)b[++num]=a[i];//num代表的是非0的个数，所以n-num就是0的个数

        }

        if(n-num>m)// 如果说0的个数比要买的书的个数还多，输出impossivle

        {

            printf("Impossible\n");

            continue;

        }

        if(n==m)//如果买的书的Ŕ个数和书的总数相等，则输出imposible

        {

            printf("Richman\n");

            continue;

        }

//        if(m==0)//如果买的书的个数为0

//        {

//            if(minn==0) printf("Impossible\n");//最小值为0，肯定不行

//            if(minn>=1) printf("%lld\n",minn-1);//否则输出最小值减去1

//            continue;

//        }

//        }

        ll ans=0,temp=inf;

        for(int i=1; i<=num; i++)

        {

            if(i<=m-n+num)ans+=b[i];

            else temp=Min(temp,b[i]);

        }

        printf("%lld\n",ans+temp-1);

    }

//        ll sum=0;

//        m-=num;//这里要找的是非0的数的个数

//        int i=1;

//        ll temp=inf;

//        while(i<=n)

//        {

//            if(a[i]==0)continue;

//            if(m>0)

//            {

//                sum+=a[i];

//                m--;

//            }

//            else if(m==0)

//                temp=Min(temp,a[i]);

//            i++;

//        }

//        // 这个时候m本已经找完了，只需要再找一本买不起的书的价格再减去1就可以了。

//    }

    return 0;

}