2015
02-22

# A Runing Game

HDU hosts sporting meeting every year. One of the most exciting events is the 10000M-running.During the match many students are running on the track. So, how about the rank list now?As we know, in a running , we rank the player according to the length everyone has passed . So if one player run 400M(one lap) farther than another player , it looks like they are running at the same position on the track , but the rank of the former is much better than the latter. Now given everyone’s position on the track , and one rank list , can you tell me whether the rank list is possible.

The first line of input gives the number of cases, T (at most 110). the first line of each case has two intergers, n,m. (1 <= n <= 100,1 <= m <= 40000,n <= m),represents there’re n players in the m-meter running.
then n lines describe every player.Each line have two intergers , Xi , Ri .Representing the i-th player is running at xi[0 , 399] meter in his recent lap, and ranks Ri in the ranklist .And the data make sure that no pair of the students have the same Xi or Ri. And the start point is at 0 in their first lap.

The first line of input gives the number of cases, T (at most 110). the first line of each case has two intergers, n,m. (1 <= n <= 100,1 <= m <= 40000,n <= m),represents there’re n players in the m-meter running.
then n lines describe every player.Each line have two intergers , Xi , Ri .Representing the i-th player is running at xi[0 , 399] meter in his recent lap, and ranks Ri in the ranklist .And the data make sure that no pair of the students have the same Xi or Ri. And the start point is at 0 in their first lap.

2
3 400
100 1
49 2
28 3
3 800
100 1
150 2
154 3

YES
NO

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXN 110

int t , n , m;
int flag;
int x[MAXN] , r[MAXN];
int tmp_x[MAXN] , tmp_r[MAXN];//存储排序后的位置以及排名

//查找哪一个比它前面的大
int search(){
for(int i = 1 ; i < n ; i++){
if(tmp_x[i] > tmp_x[i-1]) return i;
}
return 0;
}

//处理函数
void solve(){
int k;
memset(tmp_x , 0 , sizeof(tmp_x));
memcpy(tmp_r , r , sizeof(r));
sort(tmp_r , tmp_r+n);//先排序
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(tmp_r[i] == r[j]){
tmp_x[i] = x[j] ; break;//tmp_x数组赋值
}
}
}
while(k = search()){
for(int i = 0 ; i < k ; i++) tmp_x[i] += 400;//前面人加400
}
if(tmp_x[0] <= m) flag = 1;//判断是否不大于m即可
}

//主函数
int main() {
//freopen("input.txt" , "r" , stdin);
scanf("%d" , &t);
while(t--){
memset(x , 0 , sizeof(x));
memset(r , 0 , sizeof(r));
scanf("%d%d" ,&n , &m);
for(int i = 0 ; i < n ; i++)
scanf("%d%d" , &x[i] , &r[i]);
flag = 0 ; solve();
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}  

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

3. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。