每日一题之喜糖摆放

问题描述

在过年时，蓝桥村的孩子们充满活力，他们化身为捣蛋鬼，挨家挨户寻讨喜糖。他们一共收到了 NN 颗糖，每颗糖的甜度各不相同，第 ii 颗糖的甜度为 AiAi​。

然而，如何分配这些喜糖却成了一个令人困扰的问题，因为糖的数量不能完全平均分给孩子们。

蓝桥村的村长察觉到了这个困难，于是说道："我有一个问题，只要你们中有小朋友能解决，我就会提供足够的喜糖，使得你们可以均分。"

问题陈述如下：

每次可以选择将任意位置的糖果移到最后，求使得糖果按照升序排列所需的最小操作次数。

作为蓝桥村最聪明的孩子之一，你能否尝试解决这个问题呢？

输入格式

第一行输入一个整数 N(2≤N≤105)N(2≤N≤105) 表示糖果数量。

第二行输入 NN 个整数 A1,A2,⋯,AN(1≤Ai≤109)A1​,A2​,⋯,AN​(1≤Ai​≤109) 表示糖果的甜度，数据保证 A1,A2,⋯,ANA1​,A2​,⋯,AN​ 各不相同。

输出格式

输出一个整数表示答案。

这道题的意思是将给出的一组数字按升序排序，每次操作只可以将一位数字移动到最后，求最小操作数。

我们先考虑如何移动是最小的操作次数，我们只需要将需要移动的数按升序顺序移动的操作数就是最小操作数，例如 1 3 2 4 5，那么1 3 2，我们先需要移动3，移动3之后序列变成1 2 4 5 3，那么需要移动的就是4 5,。总结一下，1 2是按照升序序列，所以3需要移动，那么比3大的数都需要移动。那么我们就需要找到最长的升序序列，可以通过和排序后的序列进行比较来找，对比一下，就能找到最小的不需要移动的数字，也就是已经按照升序序列排序的数字，然后用N-不需要移动就是需要移动的次数。

#include <bits/stdc++.h>  
using namespace std;      

int main() {
  // 优化输入输出，关闭同步流，加快 cin 和 cout 的速度
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int N;                  // 定义变量 N，表示数组的大小
  cin >> N;               // 输入数组的大小 N

  vector<int> a(N);       // 定义大小为 N 的数组 a，用于存储输入的元素
  for (auto &x : a)       // 遍历数组 a，输入每个元素
    cin >> x;

  vector<int> sa = a;     // 定义数组 sa，并将其初始化为 a 的副本
  sort(sa.begin(), sa.end()); // 对 sa 进行排序，sa 现在是 a 的有序版本

  int k = 0;              // 定义变量 k，用于跟踪 sa 中已匹配的元素个数
  for (int i = 0; i < N && k < N; i++) { // 遍历数组 a
    if (a[i] == sa[k])    // 如果当前元素 a[i] 等于 sa 中的第 k 个元素
      k++;                // 匹配成功，k 自增
  }

  cout << N - k;          // 输出结果：未匹配的元素个数，即 N - k
  return 0;               
}