2018 青岛区域赛 J - Books

一时失言乱红尘 2022-04-17 04:49 215阅读 0赞

#                                                 Books #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70][]

### Sample Input ###

4
    4 2
    1 2 4 8
    4 0
    100 99 98 97
    2 2
    10000 10000
    5 3
    0 0 0 0 1

### Sample Output ###

6
    96
    Richman
    Impossible

### 题意描述： ###

给出n本书的价格和想要购买的书的数量m。购买书的规则为：每次按顺序检查每一本书，对于每一本正在检查的书，如果有足够的钱（不低于书价），将购买该书，钱数将减少该书的价格。如果钱数少于现在被检查的书的价格，将跳过那本书。求出只能购买m本书的最大钱数。如果可以带无限多的钱输出“Richman”，如果不能实现只买m本书输出“Impossible”。

### 解题思路： ###

有题意可知当n等于m是可以带无限多的钱，其他情况先找出n本书中价格为0的本数。当价格为0的本数大于m时，则为不能实现只买m本书。当价格为0的本书小于等于m时，假设m减去价格为0的本书剩下k本，买下前k本价格不为0的书（因要求的结果是只买m本书的最大钱数），找出剩下价格不为0的书中的价格最小的，输出买下前k本价格不为0书的价格之和加上剩余书中价格不为0的最低价格减一。

### 代码： ###

#include<stdio.h>
    # define inf 9999999999
    int main()
    {
    	long long a[100010],n,m,k,i,sum,t,ans,s,min;
    	scanf("%lld",&t);
    	while(t--)
    	{
    		ans=0;
    		scanf("%lld%lld",&n,&m);
    		for(i=1;i<=n;i++)
    		{
    			scanf("%lld",&a[i]);
    			if(a[i]==0)
    				ans++;
    		}
    		if(n==m)
    		{
    			printf("Richman\n");
    			continue;
    		}
    		else if(ans>m)
    		{
    			printf("Impossible\n");
    			continue;
    		}
    		k=m-ans;
    		s=1;
    		sum=0;
    		min=inf;
    		for(i=1;i<=n;i++)
    		{
    			if(a[i]==0)
    				continue;
    			if(s<=k)
    			{
    				sum+=a[i];
    				s++;
    			}
    			else if(s>k)
    			{
    				if(min>a[i])
    					min=a[i];
    			}
    		}
    		printf("%lld\n",sum+min-1);
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvbmdzYW5qaW4_size_16_color_FFFFFF_t_70]: /images/20220417/514d59be3c5b4064b058bd28f4047829.png