首页 > 试题广场 >

赛马

[编程题]赛马
  • 热度指数:1288 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

茉莉有2n匹马,每匹马都有一个速度v,现在茉莉将马分为两个队伍,每个队伍各有n匹马,两个队之间进行n场比赛,每场比赛两队各派出一匹马参赛,每匹马都恰好出场一次。茉莉想知道是否存在一种分配队伍的方法使得无论怎么安排比赛,第一个队伍都一定能获的全胜,两匹马若速度不同,那么速度快的获胜,若速度一样,则都有可能获胜。


输入描述:
第一行一个数T(T<=100),表示数据组数。

对于每组数据,第一行一个整数n , (1<=n<=100)

接下来一行,2*n个整数,第i个整数vi表示第i匹马的速度, (1
<= vi <= 1000)


输出描述:
对于每组数据,输出一行,若存在一种分配方法使得第一个队伍全胜输出YES,否则输出NO
示例1

输入

2
2
1 2 3 4
1
1 1

输出

YES
NO
import java.util.Arrays;
import java.util.Scanner;
 //排下序,第一组最差的马比第二组最强的马强就是YES,否则NO
/**
 * ***有2n匹马,每匹马都有一个速度v,现在***将马分为两个队伍,每个队伍各有n匹马,
 * 两个队之间进行n场比赛,每场比赛两队各派出一匹马参赛,每匹马都恰好出场一次。
 * ***想知道是否存在一种分配队伍的方法使得无论怎么安排比赛,第一个队伍都一定能获的全胜,
 * 两匹马若速度一样,那么速度快的获胜,若速度一样,则都有可能获胜。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            int[] nums = new int[t*2];
            for (int j = 0; j < t*2; j++) {
                nums[j] = sc.nextInt();
            }
            Arrays.sort(nums);
            if(nums[t]>nums[t-1]){
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }
    }
}

发表于 2019-08-15 16:15:11 回复(0)
题目错误,应该是若两匹马速度不一样
发表于 2019-08-15 09:02:22 回复(0)
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc = newScanner(System.in);
        intT = sc.nextInt();
        for(inti = 0; i < T; i++){
             
            intn = sc.nextInt();
            int[] vi = newint[2*n];
            for(intj = 0; j < 2*n; j++){
                vi[j] = sc.nextInt();
            }
            Arrays.sort(vi);
            if(vi[n] - vi[n-1] > 0){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
}
发表于 2019-08-08 21:44:39 回复(0)
N = int(input()) for i in range(N):
    n = int(input())
    arr = list(map(int,input().split()))
    srtd = sorted(arr, key=lambda x: x, reverse=True) if srtd[n-1]==srtd[n]: print('NO') else: print('YES')
发表于 2019-08-30 12:03:58 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/*
***有2n匹马,每匹马都有一个速度v,现在***将马分为两个队伍,每个队伍各有n匹马,两个队之间进行n场比赛,
每场比赛两队各派出一匹马参赛,每匹马都恰好出场一次。***想知道是否存在一种分配队伍的方法使得无论怎么安排比赛,
第一个队伍都一定能获的全胜,两匹马若速度一样,那么速度快的获胜,若速度一样,则都有可能获胜。
2
2
1 2 3 4
1
1 1
YES
NO
 */
public class Main {
      public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        String[] aa=new String[a];
        for(int i=0;i<a;i++){
            int b=sc.nextInt();
            int[] input=new int[2*b];

            for(int j=0;j<2*b;j++){
                input[j]=sc.nextInt();
            }
            Arrays.sort(input);
            for(int t=0;t<2*b-1;t++){
                for(int n=t+1;n<2*b;n++){
                    if(input[t]==input[n]){
                        aa[i]="NO";
                        continue;
                    }
                }
            }
            if(aa[i]==null){
                aa[i]="YES";
            }


        }
        for(int z=0;z<a;z++){
            System.out.println(aa[z]);
        }


    }
}
如果比较是否有重复值可能存在一种情况就是,重复的数字不在中间。

发表于 2019-08-17 11:39:11 回复(0)
只要保证排序后中间两个数字不相等即可保证全赢的局面
n=int(input())
A=[[] for i in range(n)]
for i in range(n):
    num=int(input())
    A[i]=list(map(int,input().split()))
    A[i]=sorted(A[i])
for i in range(n): 
    if A[i][int(len(A[i])/2)-1]==A[i][int(len(A[i])/2)]:
        print("NO")
    else:
        print("YES")

发表于 2019-08-15 17:42:48 回复(0)
n =input()
n =int(n)
 
 
defjudge(List):
    T=sorted(List)
    whileT:
        ifT[-1]>T[0]:
            T.pop(0)
            T.pop()
        else:
            returnprint('NO')
    returnprint('YES')
         
fori inrange(n):
    epoch=input()
    data =input()
    data =[
        int(i) fori indata.split()
    ]
    judge(data)
发表于 2019-08-15 10:20:23 回复(0)
排序后,前半部分总和小于后半部分,并且两边没有交集(即相同的数字,不然是平局),就行
import sys
try:
    num = int(input())
    while num:
        n = int(input())
        arr = list(map(int, sys.stdin.readline().strip().split(' ')))
        arr.sort()
        if sum(arr[:n]) < sum(arr[n:]):
            if not set(arr[:n]) & set(arr[n:]):
                print("YES")
            else:
                print("NO")
        else:
            print("NO")
        num -= 1
except:
    pass


发表于 2019-08-08 14:54:59 回复(0)
#include <stdio.h>
#include <stdlib.h>
int main(void){
    int t,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        scanf("%d",&n);
        int*v=(int*)malloc(sizeof(int)*2*n);
        for(int j=0;j<2*n;j++)
        scanf("%d",&v[j]);
        for(int j=0;j<2*n-1;j++)
        for(int k=0;k<2*n-j-1;k++){
            if(v[k]>v[k+1]){               
                int temp=v[k];
                v[k]=v[k+1];
                v[k+1]=temp;
            }
        }
     
        if(v[n-1]==v[n])
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

发表于 2019-08-03 22:04:36 回复(0)
思路不难想到,先对速度排序,然后判断中位数的那两个速度是否一样,一样就NO,不一样就YES
#include <iostream>
using namespace std;

void sort(int *arr, int size){
    for(int j=1;j<size;j++){
        for(int i=0;i<size-j;i++){
            if(arr[i]>arr[i+1]) swap(arr[i], arr[i+1]);
        }
    }
}
int main(){
    int T;
    cin>>T;
    for(int i=0;i<T;i++){
        int n;
        cin>>n;
        int arr[2*n];
        for(int j=0;j<2*n;j++){
            cin>>arr[j];
        }
        sort(arr, 2*n);
        if(arr[n-1] == arr[n]) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

发表于 2019-08-02 17:09:56 回复(1)
group=int(input())
for i in range(group):
    a=[]
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    if a[n-1]==a[n]:
        print("NO")
    else:
        print("YES")
发表于 2019-07-31 16:31:18 回复(1)
思路仿照剑指Offer数据流中的中位数,比较中间两个数的值即可
import java.util.*;
public class Main{
public static void main(String args[]){
    Scanner sc =new Scanner(System.in);
    int T=sc.nextInt();
    for(int i=0;i<T;i++){
    PriorityQueue<Integer> min=new PriorityQueue<>();        //存放n+1....2*n大的数
    PriorityQueue<Integer> max=new PriorityQueue<Integer>(11,new Comparator<Integer>(){
        public int compare(Integer s1,Integer s2){
            return s2.compareTo(s1);
        }
    });                                //存放1...n大的数
    int n=sc.nextInt();
    for(int j=0;j<2*n;j++){
        int num=sc.nextInt();
        if((j&1)==1){
            if(!min.isEmpty()&&min.peek()<num){
                min.offer(num);
                num=min.poll();
                }
                max.offer(num);
        }else{
            if(!max.isEmpty()&&max.peek()>num){
                max.offer(num);
                num=max.poll();
            }
                min.offer(num);
                }
        }
        if(min.peek()<=max.peek())                //比较中间两位数
            System.out.println("NO");
        else
            System.out.println("YES");
}
}
}

编辑于 2019-07-31 15:09:07 回复(0)