wa了几次才ac掉这道题,每次都是出现很多小小的问题,所以想把这道题详细的写一下。
首先这道题的思路是贪心+快排
我们读完题之后,一般都会想到贪心,不过我们要知道怎样贪,贪什么。
就像我们打怪一样,我们一定是去先打那个等级低,还给你加好多经验的小怪物,而不是一上来就去打BOSS然后***掉。
第一步就是去打那种回血的怪物,也就是说回馈的稳定性大于丧尸的稳定性的障碍物。
这里我们应该思考一下,打这些回血的怪物是否也要考虑优先性。
当然,我们要从小怪物打起,等我们攒够足够多的经验之后,才可以吃掉等级高的怪物呀。
所以我们要把这些回馈>丧失的障碍物给他做一个排序,丧失度低的障碍物排在前面我们先去冲撞。
接下来第二步就是要去打那些回馈<=丧失的障碍物了。这里我们需要思考一个问题,我们优先打哪些障碍物呢?
给大家举一个例子.
49 49
52 0
26 24
50 50
这是四组回馈<=丧失的障碍物,如果此时m=54,那应该输出Yes还是No呢。
假如我们先打丧失值最大的,那么我们选择52 0这一组,冲破之后我们的m只剩下2了,没法打其他障碍物了。
这里我们思考一下,我们是否应该先去冲破回复最多的,然后让我们尽可能的去冲破其他的障碍物,我们先选50 50,49 49,26 24,52 0,这样可以刚好完成任务。
如果这些障碍物丧失值足够大,我们怎样冲都不可能全部冲破,那就还不如优先去冲破回复最多的,让我们更有可能的去冲破下一个障碍物,最大可能性的完成任务。
代码有些繁琐,看看思路就好啦!!!

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T = (int)in.nval;
        for(int t=0;t<T;t++)
        {
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        long m = (long)in.nval;
        int a[][] = new int[n][2];
        int b[][] = new int[n][2];
        int ap=0,bp=0;
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            int x = (int)in.nval;
            in.nextToken();
            int y = (int)in.nval;
            if(y-x>0)
            {
                a[ap][0] = x;
                a[ap++][1] = y;
            }
            else{
                b[bp][0] = x;
                b[bp++][1] = y;
            }
        }
            boolean neng = true;
            if(ap>1)
                quickSort(0,ap-1,a);
            if(bp>1)
                quickSorts(0,bp-1,b);
            /*for(int i=0;i<ap;i++)
            {
               out.println(a[i][0]+" "+a[i][1]);
            }
            out.println();
            for(int i=0;i<bp;i++)
            {
               out.println(b[i][0]+" "+b[i][1]);
            }*/
            for(int i=0;i<ap;i++)
            {
                if(a[i][0]>m)
                {
                    neng = false;
                    break;
                }
                else{
                    m+=(a[i][1]-a[i][0]);
                }
            }
            if(neng ==false)
                out.println("No");
            else{
                for(int i=bp-1;i>=0;i--)
            {
                if(b[i][0]>m)
                {
                    neng = false;
                    break;
                }
                else{
                    m-=(b[i][0]-b[i][1]);
                }
            }
                if(neng==true)
                    out.println("Yes");
                else{
                    out.println("No");
                }

                }
        }
        out.flush();
    }
    public static void quickSort(int l,int r,int a[][])
    {
        int i=l,j=r,key=a[(l+r)/2][0],temp,temps;
        do{
            while(a[i][0]<key) i++;
            while(a[j][0]>key) j--;
            if(i<=j)
            {
                temp = a[i][0];
                a[i][0] = a[j][0];
                a[j][0] = temp;
                temps = a[i][1];
                a[i][1] = a[j][1];
                a[j][1] = temps;
                i++;
                j--;
            }
        }while(i<=j);
        if(i<r) quickSort(i,r,a);
        if(l<j) quickSort(l,j,a);
    }
     public static void quickSorts(int l,int r,int a[][])
    {
        int i=l,j=r,key=a[(l+r)/2][1],temp,temps;
        do{
            while(a[i][1]<key) i++;
            while(a[j][1]>key) j--;
            if(i<=j)
            {
                temp = a[i][1];
                a[i][1] = a[j][1];
                a[j][1] = temp;
                temps = a[i][0];
                a[i][0] = a[j][0];
                a[j][0] = temps;
                i++;
                j--;
            }
        }while(i<=j);
        if(i<r) quickSorts(i,r,a);
        if(l<j) quickSorts(l,j,a);
    }
                  }