首页 > 试题广场 >

小美的数组重排

[编程题]小美的数组重排
  • 热度指数:1015 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美有两个长度为n的数组ab
小美想知道,能不能通过重排a数组使得对于任意1 \leq i \leq n,1 \leq a_i + b_ i \leq m
将会有q次询问。

输入描述:
第一行一个整数q(1 \leq q \leq 30)。表示询问次数。
对于每一个询问:
第一行输入两个整数n,m(1 \leq n,m \leq 500)
第二行输入n个整数a_i(-500 \leq a_i \leq 500)
第三行输入n个整数b_i(-500 \leq b_i \leq 500)


输出描述:
q行,每行输出一个字符串,如果能通过重排满足条件则输出"Yes"(不含引号),否则输出"No"。
示例1

输入

2
5 3
-1 -2 3 4 5
-1 3 4  2 5
5 6
-1 -2 3 4 5
-1 3 4  2 5

输出

No
Yes

说明

对于第一个用例,无论怎么重排都不满足条件。
对于第二个用例,将数组a重排为[5,3,-2,4,-1]时满足条件。
#include <stdio.h>
#include<stdlib.h>
intcmpfun(constvoid*g,constvoid*h){
    return*(int*)g-*(int*)h;
}
intmain() {
    intq,ind[500],maxind,maxval=-600,tmp;
    scanf("%d",&q);
    intn, m,a[500],b[500],b1[500],val[500],p;
    while(scanf("%d %d", &n, &m) != EOF) {
        for(inti=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(inti=0;i<n;i++){
            scanf("%d",&b[i]);
            b1[i]=b[i];
            ind[i]=i;
        }
        qsort(a,n,sizeof(int),cmpfun);
        for(intj=0;j<n;j++){
            for(intk=0;k<n-j-1;k++){
                if(b[k]<b[k+1]){
                    tmp=b[k];
                    b[k]=b[k+1];
                    b[k+1]=tmp;
                      tmp=ind[k];
                      ind[k]=ind[k+1];
                      ind[k+1]=tmp;
                }
            }
        }
        for(intt=0;t<n;t++){
              p=ind[t];
              val[p]=a[t];
        }
        intf;
        for(f=0;f<n;f++){
            if(val[f]+b1[f]>m || val[f]+b1[f]<1){
                break;
            }
        }
        if(f==n) printf("Yes\n");
        elseprintf("No\n");
    }
    return0;
}
发表于 2023-09-02 10:39:09 回复(0)
import java.util.*;
import java.io.*;
import java.math.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(bf.readLine());
        for(int i=0;i<q;i++){
            String[] str = bf.readLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int m = Integer.parseInt(str[1]);

            int[] numsa = new int[n];
            Integer[] numsb = new Integer[n];
            str = bf.readLine().split(" ");
            for(int j=0;j<n;j++){
                numsa[j]=Integer.parseInt(str[j]);
            }
            str = bf.readLine().split(" ");
            for(int j=0;j<n;j++){
                numsb[j]=Integer.parseInt(str[j]);
            }

            Arrays.sort(numsa);
            Arrays.sort(numsb, Collections.reverseOrder());

            boolean res=true;
            for(int j=0;j<n;j++){
                int sum = numsa[j]+numsb[j];
                //System.out.println("numsa="+numsa[j]+",numsb="+numsb[j]+",i="+j+",sum="+sum);
                if(sum>=1 && sum <=m){
                    continue;
                }
                else{
                    res=false;
                    break;
                }
            }
            System.out.println(res ? "Yes" : "No");
        }
    }
}

发表于 2024-09-08 14:49:52 回复(0)
import java.util.*;
/*
基本思路:
1、因只需要判断存在性,故可直接寻找边界条件
2、对a、b进行排序
3、当(a[n-i-1] + b[i])不在[1,m]中时,即可判定No
4、遍历完后,一定存在至少一种重排方法,所以可判定为Yes
 */
public class Main {
    public static Integer[] sort(Integer[] nums){
        Arrays.sort(nums, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o1 - o2;
            }
        });
        return nums;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int i = 0; i < q; i++){
            int n = in.nextInt();
            int m = in.nextInt();
            Integer[] a = new Integer[n];
            Integer[] b = new Integer[n];
            for(int j = 0; j < n; j++){
                a[j] = in.nextInt();
            }
            for(int j = 0; j < n; j++){
                b[j] = in.nextInt();
            }
            a = sort(a);
            b = sort(b);
            int d;
            for(d = 0; d < n; d++){
                int value = a[n-d-1] + b[d];
                if(value < 1 || value > m){
                    System.out.println("No");
                    break;
                }
            }
            if(d == n){
                System.out.println("Yes");
            }

        }
    }
}


编辑于 2024-04-18 23:53:10 回复(0)
importjava.util.Arrays;
importjava.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner sc = newScanner(System.in);
        intq = sc.nextInt();
        for(inti=0;i<q;i++){
            intn = sc.nextInt();
            intm = sc.nextInt();
            Integer[] nums1 = newInteger[n];
            for(intj=0;j<n;j++){
                nums1[j] = sc.nextInt();
            }
            int[] nums2 = newint[n];
            for(intj=0;j<n;j++){
                nums2[j] = sc.nextInt();
            }
            Arrays.sort(nums1,(a,b)->b.compareTo(a));
            Arrays.sort(nums2);
            int[] res = newint[n];
            booleanflag = true;
            for(intj=0;j<n;j++){
                intnum = nums1[j] + nums2[j];
                if(num > m || num < 1){
                    flag = false;
                    break;
                }
            }
            if(flag){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
             
        }
    }
}
编辑于 2024-02-27 16:09:22 回复(0)
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
const long long mod=1e9+7;
int n,m;
int a[1005];
bool Map[1005][1005]; //邻接矩阵存图
int p[1005];         //记录当前右侧元素所对应的左侧元素
bool vis[1005];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = n/2+1; j <= n; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配,或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束,仍未找到匹配,返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= n/2; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}
void solve()
{
    cin>>n>>m;
    memset(Map,0,sizeof(Map));
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i+n];
        for(int j=1;j<=n;j++)
        {
            if(a[i+n]+a[j]>=1&&a[i+n]+a[j]<=m)
            {
                Map[j][i+n]=1;
                //cout<<j<<" "<<i<<"\n";
            }
        }
    }
    n=n*2;
    cout<<(Hungarian()==n/2?"Yes":"No")<<"\n";
}
int main()
{
    IO;
    int tn=1;
    cin>>tn;
    while(tn--)solve();
    return 0;
}
发表于 2023-10-16 17:06:12 回复(0)
q = int(input())
for i in range(q):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort(reverse=True)
    for j in range(n):
        if a[j] + b[j] > m or a[j] + b[j] < 0:
            print('No')
            break
    else:
        print('Yes')
发表于 2023-09-12 23:50:53 回复(1)
def solve(n, m, a, b):
    """
    :param n: int, 数组的长度
    :param m: int, 
    :param a: List[int], 数组 a
    :param b: List[int], 数组 b
    """
    a.sort()
    b.sort(reverse=True)
    for ai, bi in zip(a, b):
        if not 1 <= ai+bi <= m:
            return False
    return True


q = int(input())
for _ in range(q):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print("Yes" if solve(n, m, a, b) else "No")
发表于 2023-08-29 22:09:24 回复(2)