文章

68

粉丝

691

获赞

26

访问

578.4k

头像
旋转策略
P1482
发布于2020年5月26日 14:51
阅读数 7.2k

 

从左到右遍历,遇到第一个位置与值不对的数字,比如

1 2 3 7 6 5 4 8 9 10
会遇到7,此时该位置应该是4,因此应该用7,6,5,4交换,使得4归位,如果这样旋转后仍然不可,那么就 0 0吧

 

#define ll int
#define vec vector<ll>
#define inf 0x3f3f3f3f
#define MAX 500005
#define MOD 5

int main() {
	int n; 
	while (cin >> n) {
		int v2[MAX], v1[MAX], sign = 0, l = -1, r = -1;
		for (int i = 1; i <= n; i++)cin >> v2[i], v1[v2[i]] = i;
		for (int i = 1; i <= n && sign <= 1; i++) {
			if (v2[i] == i)continue;
			else{
				sign++;
				l = i, r = v1[i];
				reverse(v2 + l, v2 + r + 1);
			}
		}
		if (sign == 1)printf("%d %d\n", l, r);
		else printf("0 0\n");
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发