题目链接

调皮的依依

题目描述

老师在黑板上写下了从 到 的 个正整数。依依擦掉了其中一个数字。给定剩下的 个数字，请判断依依的说法是否可信。如果可信，输出 "Yes" 和被擦除的数字；否则，输出 "No"。

解题思路

本题的核心是验证给定的序列是否可以由 1, 2, ..., n 序列通过移除一个元素得到。一个合法的序列必须满足以下所有条件：

  1. 数量正确：依依声称只擦除一个数，所以剩下的数字数量 必须等于 。
  2. 严格升序：原始序列是严格升序的，移除一个元素后，剩下元素的相对顺序不变，因此结果序列也必须是严格升序的。这也同时保证了元素的唯一性。
  3. 范围正确：所有剩下的数字都必须在 的范围内。

基于以上分析，我们可以设计一个更鲁棒的算法：

第一步：基础检查

  • 首先，检查 是否等于 。如果不是，直接判定为不可信，输出 "No"。
  • 其次，遍历输入的数组，检查是否是严格升序的。即，对所有 i > 0，a[i] > a[i-1] 必须成立。如果不是，输出 "No"。

第二步：寻找缺失的数字

  • 如果通过了基础检查，我们现在有一个由 个不同数字组成的、严格升序的序列。我们可以通过简单的数学求和来找到缺失的数字。

  • 原始完整序列 1, 2, ..., n 的和是 。

  • 我们计算出剩下 个数字的总和 current_sum。

  • 那么，被擦除的数字就是 (n * (n+1) / 2) - current_sum。

  • 计算出这个缺失的数字后，我们还需做一个最终验证：这个数字是否在 范围内。虽然在当前逻辑下它总是满足的，但这是一种良好的编程习惯。

  • 如果所有检查都通过，则说明依依的说法可信，输出 "Yes" 和计算出的缺失数字。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long n;
    int m;
    cin >> n >> m;
    vector<long long> a(m);
    long long current_sum = 0;
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
        current_sum += a[i];
    }

    if (m != n - 1) {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 1; i < m; ++i) {
        if (a[i] <= a[i-1]) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    if (m > 0 && (a[0] < 1 || a[m-1] > n)) {
        cout << "No" << endl;
        return 0;
    }
    
    long long total_sum = n * (n + 1) / 2;
    long long missing_num = total_sum - current_sum;

    // 最终检查缺失数字的有效性
    bool missing_num_found_in_array = false;
    for(long long x : a) {
        if (x == missing_num) {
            missing_num_found_in_array = true;
            break;
        }
    }

    if (missing_num < 1 || missing_num > n || missing_num_found_in_array) {
         // 如果计算出的缺失数不在1到n的范围，或它仍然存在于数组中
         // (这意味着数组中必然有其他不在1..n范围的数或重复数，虽然升序检查已排除大部分情况)
         cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        cout << missing_num << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int m = sc.nextInt();
        long[] a = new long[m];
        long currentSum = 0;
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextLong();
            currentSum += a[i];
        }

        if (m != n - 1) {
            System.out.println("No");
            return;
        }

        for (int i = 1; i < m; i++) {
            if (a[i] <= a[i - 1]) {
                System.out.println("No");
                return;
            }
        }
        
        if (m > 0 && (a[0] < 1 || a[m - 1] > n)) {
            System.out.println("No");
            return;
        }

        long totalSum = n * (n + 1) / 2;
        long missingNum = totalSum - currentSum;
        
        boolean missingNumFoundInArray = false;
        for (long x : a) {
            if (x == missingNum) {
                missingNumFoundInArray = true;
                break;
            }
        }
        
        if (missingNum < 1 || missingNum > n || missingNumFoundInArray) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
            System.out.println(missingNum);
        }
    }
}

def solve():
    n = int(input())
    m = int(input())
    try:
        a = list(map(int, input().split()))
    except EOFError:
        a = []

    if m != n - 1:
        print("No")
        return

    if m == 0:
        if n == 1:
            print("Yes")
            print(1)
        else:
            print("No")
        return

    # 检查严格升序
    for i in range(1, m):
        if a[i] <= a[i-1]:
            print("No")
            return
            
    if a[0] < 1 or a[-1] > n:
        print("No")
        return

    total_sum = n * (n + 1) // 2
    current_sum = sum(a)
    missing_num = total_sum - current_sum

    if not (1 <= missing_num <= n) or missing_num in a:
        print("No")
    else:
        print("Yes")
        print(missing_num)

solve()

算法及复杂度

  • 算法：线性扫描
  • 时间复杂度：，其中 是依依操作后黑板上剩余的数字个数。我们只需要遍历数组一到两次。
  • 空间复杂度：，用于存储输入的数组。