PAT甲级 1067（C++）

本文主要是介绍PAT甲级 1067（C++），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

确实没思路，参考了下面的算法：【题意+分析】1067 Sort with Swap(0, i) (25 分)_24行代码AC_来老铁干了这碗代码的博客-CSDN博客但是for循环中这一段有点看不懂：

if(pos[i] != i) {
			while(pos[0] != 0) {
				swap(pos[0], pos[pos[0]]); 
				cnt++;
			}
			if(pos[i] != i) {
				swap(pos[0], pos[i]);
				cnt++;
			}

我就按照自己的理解，基于该算法思想，稍微改了改：

#include<iostream>
using namespace std;
int pos[100000];
int main() {
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int temp; cin >> temp;
		pos[temp] = i;
	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		if (pos[i] != i) {
			if (pos[0] == 0) {
				swap(pos[0], pos[i]);
				count++;
			}
			while (pos[0] != 0) {
				swap(pos[0], pos[pos[0]]);
				count++;
			}
		}
	}
	cout << count;
	return 0;
}

这样的话，每次保证至少i位置的元素（即至少一个元素）会被调整到正确的位置，因此外层for循环最多循环N次。

这篇关于PAT甲级 1067（C++）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！