首页 > 试题广场 >

小熊吃糖

[编程题]小熊吃糖
  • 热度指数:5926 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有n只小熊,他们有着各不相同的战斗力。每次他们吃糖时,会按照战斗力来排,战斗力高的小熊拥有优先选择权。前面的小熊吃饱了,后面的小熊才能吃。每只小熊有一个饥饿值,每次进食的时候,小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃,可能吃完没饱会重复上述过程,但不会选择吃撑。
现在给出n只小熊的战斗力和饥饿值,并且给出m颗糖能填饱的饥饿值。
求所有小熊进食完之后,每只小熊剩余的饥饿值。



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


输出描述:
输出n行,每行一个整数,代表每只小熊剩余的饥饿值。
示例1

输入

2 5
5 6 10 20 30
4 34
3 35

输出

4
0

说明

第一只小熊吃了第5颗糖
第二只小熊吃了第4颗糖
第二只小熊吃了第3颗糖
第二只小熊吃了第1颗糖
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    //熊类
    public static class Bear {
        int attack; //战斗力
        int hungry; //饥饿值

        public Bear(int attack, int hungry) {
            this.attack = attack;
            this.hungry = hungry;
        }
    }

    //比较器,按战斗力逆序排行
    public static class descComparator implements Comparator<Bear> {
        public int compare(Bear p1, Bear p2) {
            return p1.attack != p2.attack ? p2.attack - p1.attack : p1.hungry - p2.hungry;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Bear[] pandas = new Bear[n];
        int[] sugar = new int[m];
        for (int i = 0; i < m; i++) {
            sugar[i] = sc.nextInt();
        }
        //用哈希表保证最终结果能够不被排序打乱
        HashMap<Integer, Bear> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int attack = sc.nextInt();
            int hungry = sc.nextInt();
            pandas[i] = new Bear(attack, hungry);
            map.put(i, pandas[i]);
        }

        //按战斗力排序熊类数组
        Arrays.sort(pandas, new descComparator());
        //按糖给的能量排序糖类数组
        Arrays.sort(sugar);

        for (int i = 0; i < n; i++) {
            for (int j = m - 1; j >= 0; j--) {
                if (sugar[j] != -1 && pandas[i].hungry - sugar[j] >= 0) {
                    pandas[i].hungry -= sugar[j];
                    sugar[j] = -1; //吃完糖将其置为-1
                }
            }
        }
        //打印结果
        for (int i = 0; i < n; i++) {
            System.out.println(map.get(i).hungry);
        }
    }

}
发表于 2019-06-12 14:47:54 回复(0)
其实没啥转弯的,简单题,不过注意最后的输出顺序是按照熊一开始的出场顺序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Bear
{
    int level;
    int hungry;
    int num;
};
bool func1(Bear a, Bear b)
{
    if (a.level >= b.level)
        return true;
    else
        return false;
}
bool func2(int a, int b)
{
    if (a > b)
        return true;
    else
        return false;
}
bool func3(Bear a, Bear b)
{
    if (a.num < b.num)
        return true;
    else
        return false;
}
int main(void)
{
    int bearnum, candynum, itemp;
    cin >> bearnum >> candynum;
    vector<int> candy(candynum);
    for (int i = 0; i < candynum; i++)
    {
        cin >> itemp;
        candy[i] = itemp;
    }
    vector<Bear> bear(bearnum);
    for (int i = 0; i < bearnum; i++)
    {
        Bear temp;
        cin >> temp.level >> temp.hungry;
        temp.num = i;
        bear[i] = temp;
    }
    sort(bear.begin(), bear.end(), func1);
    sort(candy.begin(), candy.end(), func2);
    for (int i = 0; i < bearnum; i++)
    {
        int index = 0;
        while (index < candynum)
        {
            if (bear[i].hungry >= candy[index])
            {
                bear[i].hungry = bear[i].hungry - candy[index];
                candy[index] = 0;
            }
            index++;
        }
    }
    sort(bear.begin(), bear.end(), func3);
    for (auto c : bear)
    {
        cout << c.hungry << endl;
    }
    return 0;
}

发表于 2019-04-30 16:32:59 回复(0)
哈哈哈哈,其实是个大水题。刚开始看错题了,以为要每个熊吃最饱饱,然后搞了个01背包...
其实最好的办法是吃糖的时候二分,但是线性也能过,就懒得写了。
import java.util.*;
public class Main {
    public static final int M_MAX = 105, N_MAX = 15;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] candies = new int[M_MAX];
        for (int i=1; i<=m; i++) {
            candies[i] = sc.nextInt();
        }
        Bear[] bears = new Bear[N_MAX];
        for (int i=1; i<=n; i++) {
            bears[i] = new Bear(i, sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(candies, 1, m+1);
        Arrays.sort(bears, 1, n+1,
                (bear1, bear2) -> -Integer.compare(bear1.fightingValue, bear2.fightingValue));
        for (int i=1; i<=n; i++) {
            boolean flag;
            do {
                flag = false;
                for (int j=m; j>0; j--) {
                    if (candies[j] != -1 && bears[i].hungryValue >= candies[j]) {
                        bears[i].hungryValue -= candies[j];
                        candies[j] = -1;
                        flag = true;
                        break;
                    }
                }
            }
            while (flag);
        }
        Arrays.sort(bears, 1, n+1, (bear1, bear2) -> Integer.compare(bear1.No, bear2.No));
        for (int i=1; i<=n; i++) {
            System.out.println(bears[i].hungryValue);
        }
        return;
    }
}

class Bear {
    public void setHungryValue(int hungryValue) {
        this.hungryValue = hungryValue;
    }

    public int No;
    public int fightingValue;
    public int hungryValue;

    public Bear(int no, int fightingValue, int hungryValue) {
        No = no;
        this.fightingValue = fightingValue;
        this.hungryValue = hungryValue;
    }
}

编辑于 2019-01-25 01:02:49 回复(0)
贪心算法,先对熊按战斗力降序排列,然后遍历安排每只熊吃糖。每只熊进食之后,的数组都降序排一下,保证能量高的排在前面,这样就能保证每次熊的进食都是选择当前所有糖果中最能填饱肚子的。如果能够吃下当前的糖果,饥饿值就自减,糖果能量值置0;如果吃下这一颗糖会吃撑,就接着看下一棵糖,直到碰到0为止(因为排过序,后面全是0了),保存当前小熊的饥饿值。
注意在遍历的过程中注意保存小熊的编号,因为最后要按小熊的编号输出饥饿值。
n, m = map(int, input().strip().split())
hunger_fill = sorted(list(map(int, input().strip().split())), reverse=True)
bears = []
for i in range(n):
    bears.append([i] +list(map(int, input().strip().split())))
bears = sorted(bears, key=lambda x: -x[1])
res = []
for bear in bears:
    hunger = bear[2]
    for i in range(m):
        if hunger_fill[i] == 0:
            break
        if hunger_fill[i] > 0 and hunger >= hunger_fill[i]:
            hunger -= hunger_fill[i]
            hunger_fill[i] = 0
    res.append([bear[0], hunger])
    hunger_fill = sorted(hunger_fill, reverse=True)
res = sorted(res, key=lambda x: x[0])
for row in res:
    print(row[1])

编辑于 2021-04-15 12:14:30 回复(0)
  题目不难,主要是重写排序比较器
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int beer_num = scanner.nextInt();
        int suger_num = scanner.nextInt();
        int [] suger = new int[suger_num];
        for(int i=0;i<suger_num;i++){
            suger[i] = scanner.nextInt();
        }
        int [][]beer = new int[beer_num][2]; // 熊属性
        int []beer_2 = new int[beer_num];    // 记录熊的战斗力(因为后面排序会打乱位置)
        for(int i=0;i<beer_num;i++){
            beer[i][0] = scanner.nextInt();
            beer[i][1] = scanner.nextInt();
            beer_2[i] = beer[i][0];
        }
        scanner.close();
        
        // 重写比较器--降序排列
        Arrays.sort(beer, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) return o2[1] - o1[1];
                return o2[0] - o1[0];
            }
        });
        Arrays.sort(suger); // 升序(从后向前遍历)
 
        // 改变熊的饥饿值
        for(int []b : beer){
            for(int i=suger_num-1;i>=0;i--){
                if(b[1] >= suger[i]){
                    b[1] -= suger[i];
                    suger[i] = 0;
                }
            }
        }
        
        // 如果战斗力相同就输出(保证输出原先熊的顺序)
        for(int b_2 : beer_2){
            for(int[] b : beer){
                if(b[0] == b_2){
                    System.out.println(b[1]);
                }
            }
        }
    }
}


发表于 2020-09-01 17:03:38 回复(0)
下面是我的两种做法。求问第一种做法哪里错了啊,一直没法通过:
#include<bits/stdc++.h>
using namespace std;

int n, m;
int cd[100];
bool cd_used[100];
pair<int,int> atk_hry[10];
unordered_map<int, pair<int,int>&> mp;

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
    return a.first >= b.first;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        cin >> cd[i];
        cd_used[i] = false;
    }
    for(int i=0;i<n;i++) {
        cin >> atk_hry[i].first >> atk_hry[i].second;
        mp.insert(pair<int, pair<int,int>&>{i,atk_hry[i]});
    }
    sort(atk_hry, atk_hry+n, cmp);
    sort(cd, cd+m, greater<int>());
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(cd_used[j] || cd[j]>atk_hry[i].second)
                continue;
            atk_hry[i].second -= cd[j];
            cd_used[j] = true;
        }
    }
    for(int i=0;i<n;i++) {
        cout << mp.at(i).second << endl;
    }
    return 0;
}
如果自己写个带id的Bear类,然后输出之前按照id排序回来就可以通过:
#include<bits/stdc++.h>
using namespace std;

int n, m;
int cd[100];
bool cd_used[100];

class Bear{
public:
  int id;
  int atk;
  int hry;
};

Bear bear[10];

bool cmpAtk(const Bear& a, const Bear& b) {
    return a.atk > b.atk;
}

bool cmpId(const Bear& a, const Bear& b) {
    return a.id < b.id;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        cin >> cd[i];
        cd_used[i] = false;
    }
    for(int i=0;i<n;i++) {
        cin >> bear[i].atk >> bear[i].hry;
        bear[i].id = i;
    }
    sort(bear, bear+n, cmpAtk);
    sort(cd, cd+m, greater<int>());
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(cd_used[j] || cd[j]>bear[i].hry)
                continue;
            bear[i].hry -= cd[j];
            cd_used[j] = true;
        }
    }
    sort(bear, bear+n, cmpId);
    for(int i=0;i<n;i++) {
        cout << bear[i].hry << endl;
    }
    return 0;
}
请问我的第一种写法为什么不行呢?我的哈希表里的pair不是传引用的吗,难道说因为排序了,这个"引用"也会改变,就像传指针一样?
编辑于 2020-06-10 20:40:19 回复(0)
def eatSugar(n, m, sugar, bear):
    sugar = sorted(sugar, reverse = True)
    for item in sorted(bear.items(), key = lambda x:x[1], reverse = True): # 按照字典value排序
        for i in range(m):
            if item[1][1] >= sugar[i]:
                item[1][1] -= sugar[i]
                sugar[i] = 0
    for i in range(n):     # 最终输出结果要求按最早熊的顺序
        print(bear[i][1])
                    
if __name__ == "__main__":
    n, m = map(int, input().split())
    sugar = list(map(int, input().split()))
    bear = {}
    for i in range(n):
        k, v = map(int, input().split())
        bear[i] = [k, v]
    eatSugar(n, m, sugar, bear)

发表于 2019-03-27 11:42:53 回复(0)

#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
class CBear
{
public:
 CBear()
 {
 
 }
 
 int m_nFight;
 int m_nHunger;
 int m_nID;
};

bool complareSugar(const int a, const int b)
{
 return a > b;
}
bool complarePower(const CBear & a, const CBear & b)
{
 return a.m_nFight > b.m_nFight;
}
bool complareID(const CBear & a, const CBear & b)
{
 return a.m_nID <  b.m_nID;
}

int main()
{
 int nArySugar[100] = { 0 };
 int nCountSugar = 0;
 int nBear = 0;
 CBear mybear[10];
 scanf("%d", &nBear);
 scanf("%d", &nCountSugar);
 for (size_t i = 0; i < nCountSugar; i++)
 {
  scanf("%d", &nArySugar[i]);
 }
 sort(nArySugar, nArySugar + nCountSugar, complareSugar);
 for (size_t i = 0; i < nBear; i++)
 {
  scanf("%d %d", &mybear[i].m_nFight, &mybear[i].m_nHunger);
  mybear[i].m_nID = i;
 }
 sort(mybear, mybear + nBear, complarePower);
 for (size_t i = 0; i < nBear; i++)
 {
  for (size_t j = 0; j < nCountSugar; j++)
  {
   if (mybear[i].m_nHunger >= nArySugar[j])
   {
    mybear[i].m_nHunger -= nArySugar[j];
    nArySugar[j] = 0;
   }

  }
 }
 sort(mybear, mybear + nBear, complareID);
 for (size_t i = 0; i < nBear; i++)
 {
  printf("%d\n", mybear[i].m_nHunger);
 }
 return 0;
}

发表于 2019-01-28 13:45:26 回复(0)
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    public static void main( String[] args ) {
        class Bear {
            int power; int hunger;
            Bear( int p, int h ) { power = p; hunger = h; }
        }
        Scanner sc = new Scanner( System.in );
        int n = sc.nextInt();
        int m = sc.nextInt();
        LinkedList<Integer> sugers = new LinkedList<>();
        for( int i = 0; i < m; i ++ )
            sugers.add( sc.nextInt() );
        sugers.sort( (Integer i1, Integer i2) -> i2 - i1 );
        LinkedList<Bear> bears = new LinkedList<>();
        for( int i = 0; i < n; i ++ )
            bears.add( new Bear( sc.nextInt(),sc.nextInt() ) );
        LinkedList<Bear> bears_backup = new LinkedList<>();
        bears_backup.addAll( bears );
        bears.sort( ( Bear b1, Bear b2 )-> b2.power - b1.power );
        for ( Bear bear: bears ){
            Iterator<Integer> it = sugers.iterator();
            while( it.hasNext() ) {
                int tmp = it.next();
                if( bear.hunger >= tmp ) {
                    bear.hunger -= tmp;
                    it.remove();
                }
            }
        }
        for( Bear bear : bears_backup ){
            System.out.println( bear.hunger );
        }
    }
}

发表于 2019-01-19 21:00:17 回复(0)
#include <bits/stdc++.h>

using namespace std;

struct P{     int id,a,b;
};

bool cmp1(int a, int b){     return a>b;
}

bool cmp2(P p1, P p2){     return p1.a>p2.a;
}

bool cmp3(P p1, P p2){     return p1.id<p2.id;
}

int main()
{     int n,m;     while(cin>>n>>m){         int c[m];         for(int i=0;i<m;i++)             cin>>c[i];         sort(c,c+m,cmp1);         bool vis[m];         memset(vis,true,sizeof(vis));         P p[n];         for(int i=0;i<n;i++){             cin>>p[i].a>>p[i].b;             p[i].id = i;         }         sort(p,p+n,cmp2);         for(int i=0,cnt=0;i<n && cnt<m;i++)             for(int j=0;j<m;j++)                 if(vis[j] && p[i].b>=c[j]){                     p[i].b -= c[j];                     vis[j] = false;                     cnt++;                 }         sort(p,p+n,cmp3);         for(int i=0;i<n;i++)             cout<<p[i].b<<endl;     }     return 0;
}

发表于 2019-02-21 17:01:38 回复(0)
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    var inp =(await readline()).split(' ')
    var num=Number(inp[0])
    var sug=Number(inp[1])
    var suger=new Array(sug)
    suger=(await readline()).split(' ')
    suger=suger.map(Number)
    suger.sort((a,b)=>a-b)
    var bar=[]
    while(num-->0){
        tmp=(await readline()).split(' ')
        tmp=tmp.map(Number)
        bar.push(tmp)
    }
    var initBar=[].concat(bar)
    bar.sort((a,b)=>b[0]-a[0])
    for(let i=0;i<bar.length;i++){
        for(let j=suger.length-1;j>=0;j--){
            if(suger[j]<=bar[i][1]){
                bar[i][1]-=suger[j]
                suger.splice(j,1)
            }
        }
    }
    for(let i=0;i<initBar.length;i++){
        for(let j=0;j<bar.length;j++){
            if(initBar[i]==bar[j])
                console.log(bar[j][1])
        }
    }
}()

编辑于 2024-02-06 09:59:15 回复(0)
一开始在考虑用怎样的数据结构去存储这些数据,最后确定好用一个内部类,其他也就迎刃而解了
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Collections;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    // 创建内部类,封装三个属性
    static class Panda {
        int index;
        int fight;
        int eat;

        public Panda(int index, int fight, int eat) {
            this.index = index;
            this.fight = fight;
            this.eat = eat;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            //
            int n = in.nextInt();
            int m = in.nextInt();
            List<Integer> mv = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                mv.add( in.nextInt());
            }
            Collections.sort(mv, Collections.reverseOrder());
            boolean[] loc = new boolean[m];
            //
            int[] fight = new int[n];
            int[] eat = new int[n];
            List<Panda> pandas = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                fight[i] = in.nextInt();
                eat[i] = in.nextInt();
                pandas.add(new Panda(i, fight[i], eat[i]));
            }
            Collections.sort(pandas, new Comparator<Panda>() {
                @Override
                public int compare(Panda p1, Panda p2) {
                    // desc
                    return Integer.compare(p2.fight, p1.fight);
                }
            });
            //
            for (Panda p : pandas) {
                int toEat = p.eat;
                for (int i = 0; i < m; i++) {
                    if (toEat == 0) {
                        break;
                    }
                    int toGive = mv.get(i);
                    if (!loc[i] && toEat >= toGive) {
                        toEat -= toGive;
                        loc[i] = true;
                    }
                }
                eat[p.index] = toEat;
            }
            for (int i = 0; i < n; i++) {
                System.out.println(eat[i]);
            }
        }
    }
}

发表于 2023-11-29 15:45:36 回复(0)
1. 使用Map<战斗力,下标>记录熊原来位置(题中没有说明战斗力相同的情况,那么假设每个熊战斗力都不同,map的key即为熊的唯一ID)
2. 糖果和熊都进行排序
3. 遍历熊,遍历糖果,贪心选择
import java.util.Scanner;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] candy = new int[m];
        for(int i=0;i<m;i++)
            candy[i]=in.nextInt();
        int[][] bears = new int[n][2];
        Map<Integer,Integer> mapPos = new HashMap<>();
        for(int i=0;i<n;i++){
            bears[i][0] = in.nextInt();
            bears[i][1] = in.nextInt();
            mapPos.put(bears[i][0],i);
        }
        Arrays.sort(candy);
        Arrays.sort(bears,(n1,n2)->n1[0]-n2[0]);
        int[] res = new int[n];
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(bears[i][1]>=candy[j]){
                    bears[i][1]-=candy[j];
                    candy[j]=0;
                }
            }
            res[mapPos.get(bears[i][0])] = bears[i][1];
        }
        for(int i=0;i<n;i++){
            System.out.println(res[i]);
        }
    }
}


发表于 2021-08-24 10:45:22 回复(0)
n, m = list(map(int, input().split(" ")))
warh = {}

h = list(map(int, input().split(" ")))
    
for i in range(n):
    warh[i] = list(map(int, input().split(" ")))

ls = sorted(warh.items(), key=lambda x:x[1], reverse=True)
# 按战斗值排序后,去掉战斗值,第一列为第几只熊,第二列为饥饿值
wh = [[] for _ in range(n)]
for i in range(n):
    wh[i] = [ls[i][0], ls[i][1][1]]

h.sort(reverse=True)

res = [0] * n
eat = [False] * m

for i in range(n):
    for j in range(m):
        if not eat[j]:    # 糖不能重复吃
            if wh[i][1] - h[j] > 0:
                wh[i][1] -= h[j]
                eat[j] = True
            elif wh[i][1] - h[j] == 0:
                wh[i][1] = 0
                eat[j] = True
                break
    else:
        res[wh[i][0]] = wh[i][1]
for i in range(n):
    print(res[i])

发表于 2021-08-18 15:23:21 回复(0)
 import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> arrm = new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            arrm.add(sc.nextInt());//保存糖果能量
        }
        int[][] arrn = new int[n][3];
        for(int i=0;i<n;i++){
            arrn[i][0] = sc.nextInt();//战斗力
            arrn[i][1] = sc.nextInt();//饥饿值
            arrn[i][2] = i;//出场顺序
        }
        Collections.sort(arrm);//按糖果能量排序
        Arrays.sort(arrn,(o1,o2)->o2[0]-o1[0]);//按战斗力排序
        for(int i=0;i<n;i++){
            int j = arrm.size()-1;
            while(arrn[i][1]>=arrm.get(0)){//尽量填饱
                if(arrm.get(j)<=arrn[i][1]){
                    arrn[i][1]-=arrm.get(j);
                    arrm.remove(j);
                }
                j--;
            }
        }
        Arrays.sort(arrn,(o1,o2)->o1[2]-o2[2]);//按序输出
        for(int i=0;i<n;i++){
            System.out.println(arrn[i][1]);
        }
    }
}

发表于 2020-08-30 13:58:10 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // 小熊数量
        int n = input.nextInt();
        // 糖果数量
        int m = input.nextInt();
        int[] sugar = new int[m];
        // 小熊集合
        Map<Integer, Integer> bear = new HashMap<>();
        // 记录原来小熊的顺序
        Map<Integer, Integer> map = new HashMap<>();
        // 输入糖果能量值
        for (int i = 0; i < m; i++) {
            sugar[i] = input.nextInt();
        }
        // 输入小熊战斗力与饥饿值
        for (int i = 0; i < n; i++) {
            int power = input.nextInt();
            int hunger = input.nextInt();
            bear.put(power, hunger);
            // 因为战斗力不变,所以value是power,其实这里的value可以换成bear更好,不过要定义bear类而不是bear的hashmap
            map.put(i, power);
        }
        // 对糖果能量值升序排序
        Arrays.sort(sugar);
        // 按power降序排序小熊集合
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(bear.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            // 降序排序
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getKey().compareTo(o1.getKey());
            }
        });
        // 小熊吃糖果,先吃大的糖果,并且 糖果能量值 <= 饥饿值 才能吃
        for (Map.Entry<Integer, Integer> entry : list) {
            for (int i = m - 1; i >= 0; i--) {
                if (entry.getValue() >= sugar[i] && sugar[i] >= 0) {
                    entry.setValue(entry.getValue() - sugar[i]);
                    sugar[i] = -1; // 该糖果被吃了
                }
            }
        }
        // 按原来顺序输出
        for (int i = 0; i <n ; i++) {
            System.out.println(bear.get(map.get(i)));
        }

    }

}

发表于 2020-08-02 15:42:17 回复(0)
def search_max_value_no_larger_than_hunger(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r + 1) // 2
        if nums[m] > target:
            r = m - 1
        elif nums[m] == target:
            return m
        else:
            l = m
             
    return r
 
def supply_sugar(nums, target):
    while True:
        i = search_max_value_no_larger_than_hunger(nums, target)
         
        if i == -1:
            break
        else:
            if nums[i] > target:
                break
                
            target -= nums[i]
            nums.remove(nums[i])
             
            if target == 0:
                return 0
             
    return target
 
n, m = [int(i) for i in input().split()]
energies = list(map(int, input().split()))
energies.sort()
 
bearS, bearH = [], []
 
for i in range(n):
    strength, hunger = [int(i) for i in input().split()]
    bearS.append(strength)
    bearH.append(hunger)

info = sorted(enumerate(bearS), key=lambda x: x[1], reverse=True)
idxes = [i[0] for i in info]

for i in idxes:
    bearH[i] = supply_sugar(energies, bearH[i])

for i in range(n):
    print(bearH[i])

编辑于 2020-08-01 22:24:28 回复(1)
import sys

p, d = list(map(lambda line: list(map(int, line.split())), sys.stdin)), {}
p[1].sort(reverse=True)
for i in range(2, p[0][0] + 2): d[p[i][0]] = p[i][1]
for k in sorted(d, reverse=True):
    i = 0
    while i < len(p[1]):
        if p[1][i] > d[k]: i += 1
        else:
            d[k] -= p[1][i]
            del p[1][i]
for i in range(2, p[0][0] + 2): print(d[p[i][0]])

发表于 2020-07-14 18:27:59 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] food = new int[m];
        for (int i = 0; i < m; i++) {
            food[i] = sc.nextInt();
        }
        int[] zhandou = new int[n];
        int[] currentfood = new int[n];
        int[] result = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            zhandou[i] = sc.nextInt();
            currentfood[i] = sc.nextInt();
            map.put(zhandou[i], currentfood[i]);
            result[i] = zhandou[i];
        }
        Arrays.sort(food);
        Arrays.sort(zhandou);
        for (int i = n-1; i>=0; i--) {
            int foodcur = map.get(zhandou[i]);
            while(foodcur > 0) {
              int temp = foodcur;  
             for (int j = m - 1; j >= 0; j--) {
                if (food[j] > 0 && foodcur > 0 && (food[j] <= foodcur )) {
                   foodcur = foodcur - food[j];
                   food[j] = 0; 
                    j = j - 1;
                }
             }
              if (temp == foodcur) {
                  break;
              }     
            }
            map.put(zhandou[i], foodcur);
        }
        
        for (int i = 0; i < n; i++) {
            System.out.println(map.get(result[i]));
        }
        
    }
}

发表于 2020-06-30 21:12:17 回复(0)
二分超时了
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] strs = sc.nextLine().split(" ");
        int n = Integer.parseInt(strs[0]);//小熊数量
        int m = Integer.parseInt(strs[1]);//糖的数量
        strs = sc.nextLine().split(" ");
        ArrayList<Integer> candies = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            candies.add(Integer.parseInt(strs[i]));
        }
        candies.sort(Comparator.comparingInt(a -> a));
        LinkedHashMap<Integer, Integer> bears = new LinkedHashMap<>();
        List<Integer> powerlist = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            strs = sc.nextLine().split(" ");
            int power = Integer.parseInt(strs[0]);
            int hunger = Integer.parseInt(strs[1]);
            bears.put(power, hunger);
            powerlist.add(power);
        }
        powerlist.sort((a, b) -> b - a);
        for (int power : powerlist) {
            int hunger = bears.get(power);
            while (hunger > 0) {
                int index = bFind(candies, hunger);
                if (index == 0) {
                    break;
                } else if (index == candies.size() - 1) {
                    if (hunger >= candies.get(index)) {
                        hunger -= candies.remove(index);
                    }
                } else {
                    hunger -= candies.remove(index - 1);
                }
            }
            bears.put(power, hunger);
        }
        for (int power : bears.keySet()) {
            System.out.println(bears.get(power));
        }
    }

    private static int bFind(List<Integer> list, int target) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (list.get(m) <= target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}


发表于 2020-04-09 23:21:17 回复(0)