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);
}
}
京公网安备 11010502036488号