NC53681. 「土」巨石滚滚
描述
帕秋莉掌握了一种土属性魔法
她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
输入描述
输入一个整数T，代表T组数据，每组数据中：
前一行两个整数n , m，表示障碍个数和土球的稳定性
接下来一行两个整数，分别表示障碍的ai和bi
输出描述
若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)
示例1
输入:
1 5 50 49 49 52 0 5 10 26 24 70 70
输出:
No
C++14(g++5.4) 解法, 执行用时: 129ms, 内存消耗: 3448K, 提交时间: 2020-09-23 21:24:06
#include<bits/stdc++.h>
using namespace std;
int t,n;
long long m;
int a,b;
struct node {
int a,b,c;
bool operator<(const node &x) {
if(c*x.c<0)return c>x.c;
else if(c>0)return a<x.a;
else return b>x.b;
}
} p[500000+100];
int main() {
cin>>t;
while(t--) {
cin>>n>>m;
for(int i=0; i<n; i++)
scanf("%d%d",&p[i].a,&p[i].b),p[i].c=p[i].b-p[i].a;
sort(p,p+n);
for(int i=0; i<n; i++) {
m-=p[i].a;
if(m<0)break;
m+=p[i].b;
}
if(m<0)puts("No");
else puts("Yes");
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 369ms, 内存消耗: 1912K, 提交时间: 2023-02-14 20:08:13
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500010;
struct node{
ll x,y;
}a[N];
bool cmp(node x,node y){
if(x.y>=x.x&&y.y>=y.x)return x.x<y.x;
else if(x.y<x.x&&y.y<y.x)return x.y>y.y;
else return y.x-y.y>x.x-x.y;
}
int main(){
ll T,n,m;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
m-=a[i].x;
if(m<0)break;
m+=a[i].y;
}
if(m<0)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
pypy3 解法, 执行用时: 1645ms, 内存消耗: 41268K, 提交时间: 2023-01-03 01:59:10
for _ in range(int(input())):
n,m = map(int,input().split())
a = []
b = []
for i in range(n):
x,y = map(int,input().split())
if (y - x > 0):
a.append((x,y))
else :
b.append((x,y))
a.sort()
b.sort(key = lambda x : x[1],reverse = True)
for i in b:
a.append(i)
for x,y in a:
m -= x
if (m < 0):
break
m += y
if (m < 0):
print("No")
else:
print("Yes")
Python3 解法, 执行用时: 1777ms, 内存消耗: 17720K, 提交时间: 2022-07-04 11:52:50
for _ in range(int(input())):
n,m = map(int,input().split())
a = []
b = []
for i in range(n):
x,y = map(int,input().split())
if (y - x > 0):
a.append((x,y))
else :
b.append((x,y))
a.sort()
b.sort(key = lambda x : x[1],reverse = True)
a.extend(b)
for x,y in a:
m -= x
if (m < 0):
break
m += y
if (m < 0):
print("No")
else:
print("Yes")