4.喜糖摆放【算法赛】 - 蓝桥云课
问题描述
在过年时，蓝桥村的孩子们充满活力，他们化身为捣蛋鬼，挨家挨户寻讨喜糖。他们一共收到了N颗糖，每颗糖的甜度各不相同，第i颗糖的甜度为Ai。
然而，如何分配这些喜糖却成了一个令人困扰的问题，因为糖的数量不能完全平均分给孩子们。
蓝桥村的村长察觉到了这个困难，于是说道：“我有一个问题，只要你们中有小朋友能解决，我就会提供足够的喜糖，使得你们可以均分。”
问题陈述如下：
每次可以选择将任意位置的糖果移到最后，求使得糖果按照升序排列所需的最小操作次数。
作为蓝桥村最聪明的孩子之一，你能否尝试解决这个问题呢？
输入格式
第一行输入一个整数N（2≤N≤10^5）表示糖果数量。
第二行输入N个整数A1, A2, …, AN（1≤Ai≤10^9）表示糖果的甜度，数据保证A1, A2, …, AN各不相同。
输出格式
输出一个整数表示答案。
样例输入
5
1 3 2 4 5样例输出
3思路：
这道题的原理基于数组排序和元素位置调整的概念。题目要求找出将一组无序的糖果甜度数组（a）通过最少次数的“将任意位置的糖果移到最后”的操作，使其变为升序排列。然而，直接模拟这种“移动到最后”的操作可能会很复杂，因为每次移动都会影响数组中后续元素的位置。
幸运的是，我们可以采用一个更简洁的思路来解决这个问题，而不需要显式地模拟每个移动操作。这个思路基于以下几个观察：
-
排序后的数组：首先，我们对原始数组的一个副本（数组
b）进行排序，得到升序排列的数组。这个排序后的数组代表了目标状态。 -
元素匹配：然后，我们遍历原始数组（数组
a），并使用一个指针（cur）在排序后的数组（数组b）中移动，以跟踪当前“应该”出现的元素。每当遇到一个不匹配的元素时，我们意味着原始数组中的该元素不在其排序后的正确位置上。 -
计数调整：对于每个不匹配的元素，我们可以认为需要进行一次“调整”来将其放到正确的位置上。这里的“调整”并不直接对应题目中的“将任意位置的糖果移到最后”的操作，而是指逻辑上将该元素（或其影响链中的某个元素）移动到排序后的正确位置上所需的操作。由于题目只关心操作次数，而不关心具体的操作过程，因此这种计数方法是有效的。
-
贪心策略：由于数组中的元素各不相同，我们可以直接通过值来匹配元素，而不是通过索引。这种方法实际上采用了一种贪心策略：每次遇到不匹配时，我们都增加操作次数，而不关心具体的移动路径。这种策略在这个问题中是有效的，因为我们只需要知道有多少元素不在它们排序后的位置上。
-
输出结果：最后，我们输出计数器的值，即需要的最小操作次数（在这个问题的上下文中，“操作”是指将元素逻辑上移动到其排序后的正确位置上所需的“调整”次数）。
需要注意的是，虽然这种方法没有直接模拟题目中描述的“将任意位置的糖果移到最后”的操作，但它正确地计算了为了达到排序状态所需的最少“调整”次数。这里的“调整”可以理解为逻辑上的移动操作，它反映了将原始数组变为排序数组所需的最小工作量。
因此，这道题的原理是利用排序和元素位置匹配的方法，通过计数不匹配元素对来间接计算达到排序状态所需的最少操作次数。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int a[N];
int b[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n; for(int i = 1 ; i <= n ; i++){int x;cin >> x;a[i] = x;b[i] = x;}sort(b+1,b+1+n);int cur = 1,ans = 0;for(int i = 1 ; i <= n ; i++){if(a[i] != b[cur]){ans++;}else{cur++;}}cout << ans << '\n';return 0;
}
