璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:usaco22feb_photoshoot_2_b
problems
名称Photoshoot 2 B
题目编号USACO22FEB_B2
题目链接luogu.com.cn/…
来源USACO
算法分类思维, 入门_桶, 入门_数组
难易程度看懂题解

Photoshoot 2 B

想法

题目大意:将原始数列通过将数往左移动的方式变为目标数列,问最小的操作数。

首先将原始数列中每个数的位置记录,如:4的位置为5 → tong[4] = 5;

然后将目标数列转换为每个数在原始数列中的位置。此时问题就变为了将一个乱序的数列变为有序的数列。如: 5 1 4 2 3 → 1 2 3 4 5。

此时考虑任意一个数x:

  1. 当x比后续的数中的最小值还要大的时候,说明有数应该在x后面,x应往后移动。
  2. 当x比后续的数中的最小值小时,说明x的位置是合理的,x不用移动。

所以我们从后往前依次求最小值,并且通过比较第i个数与最小值来统计需要移动的数的个数。

代码实现

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	int n, temp, ans = 0;
	cin >> n;
	vector<int>tong(n+1), line(n+1);
	for (int i = 1; i <= n; ++i) {
		cin >> temp;
		tong[temp] = i;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> temp;
		line[i] = tong[temp];
	}
	int mi = 1e6;
	for (int i = n; i >= 1; --i) {
		if(line[i] < mi)
			mi = line[i];
		else
			ans++;
	}
	cout << ans;
	return 0;
}
/app/www/public/data/pages/icpc/problems/usaco22feb_photoshoot_2_b.txt · 最后更改: 2023/02/08 07:38 由 温婕莺