当前位置： 移动技术网 > 移动技术>移动开发>Android > 巨石滚滚（贪心，思维）

巨石滚滚（贪心，思维）

2020年07月09日  | 移动技术网移动技术  | 我要评论

题目

文章目录

思路：

贪心+排序，但是怎样贪呢？
设两个石头x y
从3个方面考虑：

  • 如果都是稳定性增加，则把a更小的排在前面，因为刚开始你比较弱，当然先撞小的。
  • 如果都是稳定性减少的，这个时候总的减少的是一定的，则把b更大的放在前面，使得回复更多一点。
  • 如果一个稳定性增加，一个减少，当然先撞稳定性增加的那个

代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 5e5+9;
typedef long long LL;
struct stone
{
        int a;
        int b;
}s[maxn];
bool cmp(const stone &a1,const stone &a2)
{
    int x = a1.b-a1.a;
    int y = a2.b-a2.a;
    if(x>=0&&y>=0) return a1.a<a2.a;
    if(x>=0&&y<0) return true;
    if(x<0&&y>=0) return false;
    if(x<0&&y<0) return a1.b>a2.b;
}
int main()
{
    std::ios::sync_with_stdio(false);
   int t;
   cin>>t;
   while(t--)
   {
       LL n,m;
       cin>>n>>m;
       memset(s,0,sizeof(s));
       for(int i=0;i<n;i++)
       {
           cin>>s[i].a>>s[i].b;
       }
       sort(s,s+n,cmp);
       int flag = 1;
       for(int i=0;i<n;i++)
       {
          m-=s[i].a;
           if(m<0)
        {
           printf("No\n");
          flag = 0;
          break;
        }
          m+=s[i].b;
       }
        if(flag) printf("Yes\n");
   }
    return 0;
}

本文地址：https://blog.csdn.net/qq_45769627/article/details/107201505

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网