签订协议

NC217601. 签订协议

描述

一共有n个国家来到了停战点，在协议停战签订的会场里，环形排布着n个位置，位置从1开始编号，一直到n号，每个位置上有一个国家。

签订停战协议的仪式开始了，停战协议书从1号位置开始传递，一直传递到n号位置，传到n号时，n号会再传回给1号，从而开始新的一轮传递。 停战协议签订的顺序必须按照国家的战力来排序，战力最高的最先签订停战协议。
也就是说，如果停战协议轮到了某个国家，但该国家并不是在场还未签订协议的国家中战力最强的，那么他这轮只能轮空，传给下一个国家。协议只能单向传递，不可逆传，协议书每次从n号传到1号手上算是一轮。不满一圈的也算一轮。各个国家战力保证不相同。为了停战协议的顺利签订，会场组织者向你求助，求最少传递多少轮可以完成协议的签订。

输入描述

第一行，一个正整数 n，表示有 n 个国家参与
第二行n个正整数，第  个数表示落座在第 i 个位置的国家的战力值

输出描述

第一行，一个正整数，完成签订协议的最少轮数。

示例1

输入:

5
1 5 8 4 3

输出:

说明:

第一轮：8

第二轮：5 4 3

第三轮：1

示例2

输入:

10
11 8 5 7 1 6 2 3 4 10

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 271ms, 内存消耗: 6640K, 提交时间: 2023-07-05 20:10:17

#include<bits/stdc++.h>
using namespace std;
int n,ans=1;
struct node{int x,id;}a[800005];
bool cmp(node x,node y){return x.x>y.x;}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(int i=2;i<=n;i++)if(a[i].id<a[i-1].id)++ans;
	cout<<ans<<endl;
	return 0;
}

C++(clang++11) 解法, 执行用时: 247ms, 内存消耗: 6632K, 提交时间: 2021-02-27 14:47:31

#include <bits/stdc++.h>
using namespace std;
int n,mem[800005],p[1000005],ans=1,last;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>mem[i];
		p[mem[i]]=i;
	}
	for(int i=1000000;i;i--){
		if(p[i]){
			if(p[i]<last)
				ans++;
				last=p[i];
		}
	}
	cout<<ans;
	return 0;
}

Python3(3.9) 解法, 执行用时: 1116ms, 内存消耗: 133912K, 提交时间: 2021-01-30 17:13:25

n = int(input())
lst = list(map(int, input().split()))
l = []
for i in range(n):
    l.append( (i, lst[i]) )
l.sort(key = lambda x : x[1], reverse = True)
cnt = 1
for i in range(n - 1):
    if l[i][0] > l[i + 1][0]:
        cnt += 1
print(cnt)