首页 > 试题广场 >

小美的数组操作2

[编程题]小美的数组操作2
  • 热度指数：1558 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小美拿到了一个数组，她每次可以进行如下操作：
选择两个元素，一个加 1，另一个减 1。
小美总共进行了k次操作。她希望你回答最终数组是否是非降序，你能帮帮她吗？
请注意，元素可能会被减成负数！

输入描述:
第一行输入一个正整数 t，代表询问次数。
每次询问首先第一行输入两个正整数n和k，代表数组长度和操作次数。
接下来的一行输入n个正整数 a_i，代表初始数组。
接下来的k行，每行输入两个正整数u,v，代表使得第u个元素加 1，第v个元素减 1。
1\leq t,n,k,a_i \leq 100


输出描述:
输出t行，每行输出该次询问的答案。
如果数组变成了非降序，则输出"Yes"。否则输出 "No"。
示例1

输入

2
3 2
3 4 5
2 3
1 2
3 2
3 4 5
2 3
2 3

输出

Yes
No

说明

第一组询问，操作两次后数组变成[4,4,4]，为非降序。
第二组询问，操作两次后数组变成[3,6,3]，并不是非降序。
算法知识视频讲解
添加回答
轮殇永忘头像 轮殇永忘
直接跟着题目思路走呗

#include <iostream>
using namespace std;
intt,n,k,a[500];
 
intmain() {
    cin>>t;
    while(t--) {
        cin>>n>>k;
        for(inti=1;i<=n;i++)
            cin>>a[i];
        for(inti=1;i<=k;i++)
        {
            intu,v;
            cin>>u>>v;
            a[u]++;
            a[v]--;
        }
        for(inti=2;i<=n;i++)
        {
            if(a[i]<a[i-1])
            {
                cout<<"No"<<endl;
                break;
            }
            if(i==n) cout<<"Yes"<<endl;
        }
         
    }
}

发表于 2023-11-06 17:32:22 回复(0)
Java
青春猪头少年不会没有offer头像 青春猪头少年不会没有offer
简单模拟 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- != 0) {
            int n = in.nextInt(), k = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) a[i] = in.nextInt();
            while (k-- != 0) {
                int u = in.nextInt(), v = in.nextInt();
                a[u - 1]++;
                a[v - 1]--;
            }
            boolean f = true;
            for (int i = 1; i < n; ++i) {
                if (a[i] < a[i - 1]) {
                    f = false;
                    break;
                }
            }
            if (f) System.out.println("Yes");
            else System.out.println("No");
        }
    }
}


编辑于 2023-12-26 21:02:08 回复(0)
Java
华南大番薯头像 华南大番薯 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
            }
            for (int j = 0; j < k; ++j) {
                int u = in.nextInt();
                int v = in.nextInt();
                arr[u - 1]++;
                arr[v - 1]--;
            }
            boolean sorted = true;
            for (int i = 1; i < n; ++i) {
                if (arr[i] < arr[i - 1]) {
                    sorted = false;
                    break;
                }
            }
            System.out.println(sorted ? "Yes" : "No");
        }
    }
}

发表于 2023-11-07 00:04:57 回复(0)
sivan941头像 sivan941 
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    for i in range(k):
        i1, i2 = map(int, input().split())
        nums[i1 - 1] += 1
        nums[i2 - 1] -= 1
    print("Yes" if sorted(nums) == nums else "No")

发表于 2023-09-21 14:11:55 回复(0)
Python
牛客42029224号头像 牛客42029224号
#Python
whileTrue:
    try:
        c = list()
        n = int(input())
        fori in range(n):
            a = list(map(int, input().split()))
            b = list(map(int, input().split()))
            forj in range(a[1]):
                c.append([])
                c[j] = list(map(int, input().split()))
                b[c[j][0] - 1] += 1
                b[c[j][1] - 1] -= 1
            fork in range(a[0] - 1):
                ifb[k] > b[k + 1]:
                    print("No")
                    break
            else:
                print("Yes")
 
    except:
        break

发表于 2023-09-07 00:00:00 回复(0)
Python
求工作的磨洋工匠人很完美头像 求工作的磨洋工匠人很完美
def isNonDecreasing(nums):
    n = len(nums)
    fori in range(n-1):
        ifnums[i] > nums[i+1]:
            returnFalse
    returnTrue
 
t = int(input())  # 读取询问次数
 
for_ in range(t):
    n, k = map(int, input().split())  # 读取数组长度和操作次数
    nums = list(map(int, input().split()))  # 读取初始数组
     
    for_ in range(k):
        u, v = map(int, input().split())  # 读取操作
        nums[u-1] += 1
        nums[v-1] -= 1
     
    result = isNonDecreasing(nums)
    ifresult:
        print("Yes")
    else:
        print("No")
发表于 2023-08-25 12:01:38 回复(0)
Java
无鱼不欢头像 无鱼不欢
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = Integer.parseInt(in.nextLine());
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();  // 数组长度
            int k = in.nextInt();  // 操作次数

            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }



            for (int i = 0 ; i < k; i++) {
                int u = in.nextInt(); //u  +1
                int v = in.nextInt(); //v  -1
                arr[u - 1] = arr[u - 1] + 1;
                arr[v - 1] = arr[v - 1] - 1;
            }

            int count = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i - 1] <= arr[i]) {
                    count++;
                }
            }

            if (count == (n - 1) ) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}
发表于 2023-08-25 11:51:25 回复(0)
NewThink头像 NewThink
    做不来，大概思路，不知道对不对
    特殊情况
        只有一个数：不用改变，return 0
        有两个数：一个出现次数为n-1，且 sum % n != 0，不能通过改变使得全部相同，return 0
    一般情况
        sum % n == 0：能通过改变使得全部相同，计算平均值，计算所有值到平均值的距离之和 / 2
        sum % n ！= 0：牺牲一个数，最多可以使 n-1 个数相同；
            牺牲最大值 or 最小值？？？
            最保险的做法：选择最大或最小其中一个牺牲，计算其余数的平均值avg
                avg > xxx.5 应该取ceiling
                avg < xxx.5 应该取floor
                计算大于avg的数到avg的距离和 与 小于avg的数到avg的距离和，取大的那个
            选择牺牲最大或最小中的小的那个返回
发表于 2023-08-24 11:37:57 回复(1)
提交观点

问题信息

来自：美团2023年秋招笔试...
难度：
8条回答 1823浏览

热门推荐

相关试题

小美的数组操作2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号