CF33A What is for dinner?

传送门

题目

鲨鱼有 $n$ 颗牙齿，分别分布于 $m$ 行上，第 $i$ 颗牙齿有一个初始活力值 $c_i$。鲨鱼有 $k$ 个食物想要吃，但是，每吃掉一个食物就要消耗某一排牙齿的每一颗牙齿各 $1$ 点活力，而鲨鱼必须保证每个牙齿的剩余活力不能到负数。试求鲨鱼最多能吃到的食物个数。

分析

不难发现每排最小活力值的牙齿是整排牙齿能吃的食物的数量，用 ans 累加的最多吃的食物的量。

求最小值

将每排牙床赋尽量大的值，通过比较找到最小值

但是

我们只讨论了鲨鱼牙齿不好的情况，如果牙齿能吃的食物量大于总食物量，直接输出食物的量即可。

若存在空牙排，就要判断是否加上当前的最小活力，因为牙床排为空时，活力值为我们赋的的最大值。要舍去这种情况，所以定义一个 bool类型的数组，判断牙床是否存在牙。

代码奉上

#include<iostream>//cin,cout输入输出 
#include<limits>//用于检测整型数据数据类型的值的范围
#include<cmath>//包含min 
using namespace std;
int n,m,k,ans;//鲨鱼有n颗牙齿，分别分布于m行上，鲨鱼有k个食物想要吃。 
int teeth[1001];//每排最小活力值 
bool have[1001];//是否存在当前排的牙齿 
int main(){
  cin>>n>>m>>k;
  //要用比较来找到活力值最小的牙齿，让初始值尽量大 
  for(int i=1;i<=m;i++){
    teeth[i]=INT_MAX;//INT_MAX为int的最大值 在 limits 头文件中 
  }
  for(int i=1;i<=n;i++){//遍历牙 
    int x,c;//x，c分别表示这个牙齿所在的行数和初始活力值。
    cin>>x>>c;
    teeth[x]=min(teeth[x],c);//找最小活力牙齿 
    have[x]=1;//当前排存在牙齿 
  }
  for(int i=1;i<=m;i++){//遍历排 
    if(!have[i])continue;//不存在牙齿直接跳过 
    ans+=teeth[i];//计算吃最多的食物的数量 
    if(ans>k){//超过食物上限，只能吃到最多的食物数 
      ans=k;//更新最多的食物量 
      break;//跳出 
    }
  }
  cout<<ans;//输出答案 
  return 0;//完结撒花
  //@^-^@
}