[08]小熊吃糖-拼多多2018秋

1.题目描述

有n只小熊，他们有着各不相同的战斗力。每次他们吃糖时，会按照战斗力来排，战斗力高的小熊拥有优先选择权。前面的小熊吃饱了，后面的小熊才能吃。每只小熊有一个饥饿值，每次进食的时候，小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃，可能吃完没饱会重复上述过程，但不会选择吃撑。 现在给出n只小熊的战斗力和饥饿值，并且给出m颗糖能填饱的饥饿值。 求所有小熊进食完之后，每只小熊剩余的饥饿值。

• 输入描述:
  第一行两个正整数n和m，分别表示小熊数量和糖的数量。（n <= 10, m <= 100） 第二行m个正整数，每个表示着颗糖能填充的饥饿值。 接下来的n行，每行2个正整数，分别代表每只小熊的战斗力和当前饥饿值。 题目中所有输入的数值小于等于100。
• 输出描述:
  输出n行，每行一个整数，代表每只小熊剩余的饥饿值。
• 输入示例:

  2 5
  5 6 10 20 30
  4 34
  3 35
  

• 输出示例:

  4
  0
  

• 说明
  第一只小熊吃了第5颗糖(30)
  第二只小熊吃了第4颗糖(20)
  第二只小熊吃了第3颗糖(10)
  第二只小熊吃了第1颗糖(5)

2.题目解析

需要用到排序算法：按战斗力对小熊们排序；按能填充的饥饿值对糖排序。
注意

1. 最终答案需要按照小熊输入的顺序进行输出，在排序之后要记录一下这个信息。
2. 一个小熊可能会吃多块糖

3.参考答案

#include <bits/stdc++.h>
using namespace std;
// 小熊结构体
struct Bear{
  int finger; // 战斗力
  int hunger; // 饥饿值
  int id;     // 编号
};
bool cmpBear(Bear a,Bear b){
    return a.finger > b.finger;
}
bool cmpBearById(Bear a,Bear b){
    return a.id < b.id;
}
bool cmpSugar(int a,int b){
    return a > b;
}
int main() {
   int n = 0;// 小熊数量
   int m = 0;// 糖数
   scanf("%d%d",&n,&m);
   int sugars[m];
   for(int i=0;i<m;++i){
       scanf("%d",&sugars[i]);
   }
   Bear bears[n];
   for(int i=0;i<n;++i){
       scanf("%d%d",&bears[i].finger,&bears[i].hunger);
       bears[i].id = i; // 记录进入的顺序
   }
   // 糖果按照大小排序
   sort(sugars,sugars+m,cmpSugar);
   // 小熊按照战斗力排序
   sort(bears,bears+n,cmpBear);
   
   for(int i=0;i<n;++i){
       for(int j=0;j<m;++j){
           if(sugars[j] != 0 && bears[i].hunger >= sugars[j]){
               // bears[i].hunger = bears[i].hunger - sugars[j];
               bears[i].hunger -= sugars[j];
               sugars[j] = 0;
           }
       }
   }
   sort(bears,bears+n,cmpBearById);// 按照进入顺序重新排序
   for(int i=0;i<n;++i){
       printf("%d\n",bears[i].hunger);
   }
   
   return 0;
}

#include <bits/stdc++.h>
using namespace std;
// 小熊结构体
struct Bear{
  int finger; // 战斗力
  int hunger; // 饥饿值
  int id;     // 编号
};
bool cmpBear(Bear a,Bear b){
    return a.finger > b.finger;
}
bool cmpBearById(Bear a,Bear b){
    return a.id < b.id;
}
bool cmpSugar(int a,int b){
    return a > b;
}
int main() {
   int n = 0;// 小熊数量
   int m = 0;// 糖数
   scanf("%d%d",&n,&m);
   int sugars[m];
   for(int i=0;i<m;++i){
       scanf("%d",&sugars[i]);
   }
   Bear bears[n];
   for(int i=0;i<n;++i){
       scanf("%d%d",&bears[i].finger,&bears[i].hunger);
       bears[i].id = i; // 记录进入的顺序
   }
   // 糖果按照大小排序
   sort(sugars,sugars+m,cmpSugar);
   // 小熊按照战斗力排序
   sort(bears,bears+n,cmpBear);
   // 记录糖果是否被吃了
   bool eated[m];
   fill_n(eated,m,false);
   
   for(int i=0;i<n;++i){
       for(int j=0;j<m;++j){
           if(eated[j] == false && bears[i].hunger >= sugars[j]){
               // bears[i].hunger = bears[i].hunger - sugars[j];
               bears[i].hunger -= sugars[j];
               eated[j] = true;
           }
       }
   }
   sort(bears,bears+n,cmpBearById);// 按照进入顺序重新排序
   for(int i=0;i<n;++i){
       printf("%d\n",bears[i].hunger);
   }
   
   return 0;
}

#include <bits/stdc++.h>
using namespace std;
// 小熊结构体
struct Bear{
  int finger; // 战斗力
  int hunger; // 饥饿值
  int id;     // 编号
};
struct Sugar{
  int value; // 糖果数值
  bool eated; // 是否被吃掉
};
bool cmpBear(Bear a,Bear b){
    return a.finger > b.finger;
}
bool cmpBearById(Bear a,Bear b){
    return a.id < b.id;
}
bool cmpSugar(Sugar a,Sugar b){
    return a.value > b.value;
}
int main() {
   int n = 0;// 小熊数量
   int m = 0;// 糖数
   scanf("%d%d",&n,&m);
   Sugar sugars[m];
   for(int i=0;i<m;++i){
       scanf("%d",&sugars[i].value);
       sugars[i].eated = false;
   }
   Bear bears[n];
   for(int i=0;i<n;++i){
       scanf("%d%d",&bears[i].finger,&bears[i].hunger);
       bears[i].id = i; // 记录进入的顺序
   }
   // 糖果按照大小排序
   sort(sugars,sugars+m,cmpSugar);
   // 小熊按照战斗力排序
   sort(bears,bears+n,cmpBear);
   
   for(int i=0;i<n;++i){
       for(int j=0;j<m;++j){
           if(sugars[j].eated == false && bears[i].hunger >= sugars[j].value){
               // bears[i].hunger = bears[i].hunger - sugars[j];
               bears[i].hunger -= sugars[j].value;
               sugars[j].eated = true;
           }
       }
   }
   sort(bears,bears+n,cmpBearById);// 按照进入顺序重新排序
   for(int i=0;i<n;++i){
       printf("%d\n",bears[i].hunger);
   }
   
   return 0;
}

#include <algorithm>
#include <cstdio>
using namespace std;

struct Bear {
  int fight; // 战斗力
  int hunger; // 饥饿值
  int id;    // 序号
};
bool cmp(Bear& a,Bear& b){
  return a.fight > b.fight;
}

int main() {
  int n = 0; // 小熊数量
  int m = 0; // 糖的数量
  scanf("%d %d", &n, &m);

  // 获取糖果
  int a[m];
  for (int i = 0; i < m; ++i) {
    scanf("%d", &a[i]);
  }

  // 获取小熊战斗力和饥饿值信息
  Bear b[n];
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &b[i].fight, &b[i].hunger);
    b[i].id = i; // 保存录入编号
  }

  // 小熊按照战斗力排序
  sort(b, b + n,cmp);
 
  // 根据战斗力分配糖果
  int res[n];  // 小熊剩余饥饿值
  bool v[m];   // 糖果是否被吃了
  fill_n(v,m,false); // false默认糖果未被吃
  for (int i = 0; i < n; ++i) { // 遍历战斗力排序后的小熊
    int index = -1;// 表示找到糖的ID小于饥饿值最大的糖
    for (int j = 0; j < m; ++j) { // 遍历糖
      // 选择小熊
      if (!v[j]                               // 糖果未被吃
          && b[i].hunger >= a[j]              // 小熊能吃的下糖
          && (index == -1 || a[j] > a[index]) // 第一个被吃的糖或者最大可被吃的糖
      ) {
        index = j;
      }
    }

    // 已经找到糖
    if (index != -1) {
      b[i].hunger -= a[index]; // 减少饥饿值
      v[index] = true; // 表示糖果已经被吃了
      --i;
    } else {
      // 没有找到糖保留饥饿值
      res[b[i].id] = b[i].hunger;
    }
  }

  // 输出剩余的饥饿值
  for (int i = 0; i < n; ++i) {
    printf("%d\n", res[i]);
  }
  return 0;
}

牛客题目