HihoCoder - 1631 Cats and Fish（思维）-白红宇

HihoCoder - 1631 Cats and Fish（思维）

阅读量：3899 次

发布时间：2019-05-23

本文共 2173 字，大约阅读时间需要 7 分钟。

【题目】

描述

There are many homeless cats in PKU campus. They are all happy because the students in the cat club of PKU take good care of them. Li lei is one of the members of the cat club. He loves those cats very much. Last week, he won a scholarship and he wanted to share his pleasure with cats. So he bought some really tasty fish to feed them, and watched them eating with great pleasure. At the same time, he found an interesting question:

There are m fish and n cats, and it takes ci minutes for the ith cat to eat out one fish. A cat starts to eat another fish (if it can get one) immediately after it has finished one fish. A cat never shares its fish with other cats. When there are not enough fish left, the cat which eats quicker has higher priority to get a fish than the cat which eats slower. All cats start eating at the same time. Li Lei wanted to know, after x minutes, how many fish would be left.

输入

There are no more than 20 test cases.

For each test case:

The first line contains 3 integers: above mentioned m, n and x (0 < m <= 5000, 1 <= n <= 100, 0 <= x <= 1000).

The second line contains n integers c1,c2 … cn, ci means that it takes the ith cat ci minutes to eat out a fish ( 1<= ci <= 2000).

输出

For each test case, print 2 integers p and q, meaning that there are p complete fish(whole fish) and q incomplete fish left after x minutes.

样例输入

2 1 118 3 51 3 44 5 15 4 3 2 1

样例输出

1 00 10 3

【题意】

给定m只鱼和n只猫，给定猫i吃掉一条鱼的时间c[i]，所有的猫同时开始吃鱼，吃完一条马上吃下一条。当鱼不充足时，吃的比较快的猫优先吃鱼。那么问题来了，当时间到了x时，剩下的完整的鱼和不完整的鱼还有多少？

【思路】

这题目读起来就很舒服了，一点生僻词汇也没。数据不大，心安。但是实现起来花了我近一个小时你敢信？

首先排序，剩下完整的鱼的数目没什么问题，按时间分一条减一条就好了，关键是不完整的鱼需要考虑到最后一条鱼开始吃的时间到x是否小于c[i]。刚开始考虑定义个数组记录状态，无果。换个思路，我们只需要比较猫i可以吃的鱼所需要花掉的总时间跟x就好了，所以这里定义一个数组a[]用来存猫可食用的鱼的数目。

还是太菜了。

【代码】

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long int ll;main(){ int m,n,x,t,c[105],a[105]; while(cin>>m>>n>>x) { mem(a,0); for(int i=1;i<=n;i++) cin>>c[i]; sort(c+1,c+n+1); int c1=m,c2=0; for(int i=0;i

转载地址：http://nyben.baihongyu.com/

你可能感兴趣的文章