NC200617. L-JAJA_Xin的小心思
描述
输入描述
多测试用例，保证 ∑n≤107；
每组用例的第一行包含两个整数n和m（1≤n≤105,1≤m≤109）。
接下来输入有n行，第i行有两个整数ai和bi(1≤ai,bi≤109, bi<ai)。
输出描述
请输出需要压缩几个袋子。
如果无法装进行李箱，请输出-1。
示例1
输入:
3 10 5 2 6 4 4 3
输出:
2
说明:
JAJA_Xin可以压缩第一和第二个袋子，因此在这些压缩之后，大小之和将2+4+4=10≤10。请注意，压缩任何单独一个袋子不足以把所有行李都装进行李箱（例如，压缩第三个袋子，大小之和5+6+3=14>10）示例2
输入:
3 8 5 3 6 4 4 2
输出:
-1
说明:
JAJA_Xin压缩所有的袋子，大小之和将3+4+2=9>8，无法装进行李箱。C++14(g++5.4) 解法, 执行用时: 894ms, 内存消耗: 1124K, 提交时间: 2020-05-17 19:54:43
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005];
ll n,m;
ll sum;
ll h,k;
ll ans;
int main(){
while(cin>>n>>m){
sum=0;
for (int i=0;i<n;i++){
cin>>h>>k;
sum+=h;
a[i]=h-k;
}
sort(a,a+n);
int i=n-1;
ans=0;
while(sum>m && i>=0){
sum-=a[i];
ans++;
i--;
}
if (sum>m){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 298ms, 内存消耗: 14748K, 提交时间: 2020-07-17 12:00:48
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a,b;
}R[100005];
bool cmp(node x,node y)
{
return x.a-x.b>y.a-y.b;
}
int main()
{
int i,n,m,ans;
long long s;
while(~scanf("%d%d",&n,&m))
{
ans=s=0;
for(i=0;i<n;i++)scanf("%d%d",&R[i].a,&R[i].b),s+=R[i].a;
sort(R,R+n,cmp);
for(i=0;s>m&&i<n;i++)s+=R[i].b-R[i].a,ans++;
if(i==n&&s>m)ans=-1;
printf("%d\n",ans);
}
}