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:
- 当x比后续的数中的最小值还要大的时候,说明有数应该在x后面,x应往后移动。
- 当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 由 温婕莺