首页 > 试题广场 >

度度熊的工作

[编程题]度度熊的工作

热度指数：947 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

老板给度度熊分配了 $\mathit n$ 个工作，第 $\mathit i$ 个工作需要耗费 $a_i$ 单位时间，每个工作必须老板给定的限制时间 $b_i$ 前完成。
度度熊从 $\text 0$ 时刻开始工作，在同一时间度度熊手上只能做一件工作，度度熊想知道他是否能把所有工作都完成呢？

输入描述:

第一行一个数表示数据组数。
每组数据第一行一个数。
接下来行每行两个数表示,。

输出描述:

每组数据输出一行，如果度度熊能完成他的工作输出"Yes"不然输出“No”。

示例1

输入

输出

Yes

说明

从前往后依次做每个工作即可完成。

算法知识视频讲解

小浣熊zzZZ

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int k=0;
    cin>>k;
    for(int i=0;i<k;i++){
        int n=0;
        cin>>n;
        vector<pair<int,int>> a;
        for(int j=0;j<n;j++){
            int x=0,y=0;
            cin>>x>>y;
            a.push_back({x,y});
        }
        sort(a.begin(),a.end(),[](pair<int,int> x1,pair<int,int> x2){
            if(x1.second==x2.second) return x1.first<x2.first;
            return x1.second<x2.second;
        });
        int time=0;
        int j=0;
        for(;j<n;j++){
            time+=a[j].first;
            if(time>a[j].second) break;
        }
        if(j==n) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

发表于 2021-08-17 22:46:19 回复(0)

夏川_

银行家算法

发表于 2022-03-04 18:34:51 回复(0)

香菜君

// JavaScript - V8
let circle = parseInt(readline())
while(circle--) {
  let flag = true
  let nums = parseInt(readline())
  while(nums--) {
  let arr = (readline()).split(' ')
    if(parseInt(arr[0]) > parseInt(arr[1])) {
      flag = false
    }
  }
  if (flag) {
  console.log('Yes')
  } else {
  console.log('No')}
  }

编辑于 2021-09-07 17:02:18 回复(3)

梦特别娇

 bool baidu(multimap<int,int>mp)
    {
        int time=0;
        for(auto x:mp)
        {
            time+=x.second;
            if(x.first<time)
            return false;
        }
        return true;
    }
int main()
{   
    int n,m,k;
    cin>>n;  
    vector<bool>ans;
   for(int i=0;i<n;i++)
   {    cin>>m;
   multimap<int,int>mp;
    for(int j=0;j<m;j++)
    {
        int a,b;
        cin>>a;cin>>b;
        mp.insert(make_pair(b,a));
        
    }
        ans.push_back(baidu(mp));     
   }
   for(auto x:ans)
   {
    if(x)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
   }
}

利用mulitmap按key值排序用bi作key ai作value 自测能过但是用例一个都不通过求大神指点

编辑于 2022-06-17 14:27:40 回复(0)

JavaScript

牛客476721401号

let circle = parseInt(readline())
while(circle--) {
let flag = true
let nums = parseInt(readline())
let sum=0;
while(nums--) {
let arr = (readline()).split(' ')
sum=sum+parseInt(arr[0])
if(sum > parseInt(arr[1])) {
flag = false
}
else {
;
}
}
if (flag) {
console.log('Yes')
} else {
console.log('No')}

}

#不知道为什么有2组案例没有过感觉没有错了啊

发表于 2021-09-21 12:14:40 回复(2)

牛客小浩

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

typedef struct node{
    int a;
    int b;
    node(int a1,int b1){
        a=a1;
        b = b1;
    }
}nodes,*pnode;
bool cmp(pnode n1,pnode n2){
    return n1->b<n2->b;
}
int main(){
    int n;
    cin>>n;
    //cin>>k;
    while(n>0){
        int k=0;
        cin>>k;
        vector<pnode> nodes;
        for(int i=0;i<k;i++){
           int a,b;
           cin>>a>>b;
           pnode temp = new node(a,b);
           nodes.push_back(temp);
        }
        //全部的工作
    sort(nodes.begin(),nodes.end(),cmp);//时间从小到大
    //遍历
    int sumtime =0;
    bool flage = true;
    for(auto nn:nodes){
        sumtime+=(nn->a);
        //cout<<sumtime<<"----"<<endl;
        if(sumtime>(nn->b)){
            cout<<"No"<<endl;
           flage = false;
            break;
        }
    }
    if(flage){
        cout<<"Yes"<<endl;
    }
        
    
     //清空
     n--;
    }

return 0;
}

发表于 2021-07-22 17:04:03 回复(0)

牛客-新蜗牛

#include <cstdio>
#include <algorithm>
using namespace std;
int t,n;
struct node { //定义结构体用来存储每个任务
    int a,b;
};
bool cmp(node x,node y){ //sort排序的函数
    return x.b<y.b;
}
bool Complete(node sad[],int n){ //判断是否能完成任务
         int sum =0;
         for(int i =0;i<n;i++){
             sum+=sad[i].a;
             if(sad[i].b<sum) return false;
         }
return true;
}

int main(){
scanf("%d",&t);
int index=0;

while(index<t){
scanf("%d",&n);
node sad[n];
int tempIndex = 0;
while(tempIndex<n){
scanf("%d %d",&sad[tempIndex].a,&sad[tempIndex].b);
tempIndex++;
};
sort(sad,sad+n,cmp);
if(Complete(sad,n)){
printf("Yes\n");
}else{
printf("No\n");
};

index++;
};

}

发表于 2021-06-15 15:50:08 回复(0)

ww_info

# 排序后进行加和时间复杂度过高
g = int(input())
for _ in range(g):
    tasks = int(input())
    ddl = []
    for i in range(tasks):
        t, d = map(int, input().split())
        ddl.append([t, d])
    ddl.sort(key = lambda x: x[1])
    res = 0
    for time, deadline in ddl:
        if res + time > deadline:
            print("No")
        else:
            res += time
    print("Yes")

编辑于 2021-05-17 21:48:07 回复(0)