【模拟】签订协议
战争尾声
https://ac.nowcoder.com/acm/contest/11038/A
签订协议
nowcoder 217601
题目大意
给出n个数，现在有一个协议书，让你从1传到n，然后传回1，继续传下去
对于第i个数，如果前面i-1个数已经匹配过了，那么当协议书传过来时即可匹配，否则无法匹配
我让你让所有数匹配最少传多少圈（向上取整）
解题思路
如果直接暴力枚举会TLE
当匹配完值为的点后需要匹配值为
的点
那么可以按排序，这样得到匹配的数的顺序
设为当前数的初始位置
如果那么不用多传一圈
否则要多传一圈
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, ans;
struct node
{
int v, s;
}a[800010];
bool cmp(node x, node y)
{
return x.s > y.s;//按给出的值排序
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i].s);
a[i].v = i;//记录初始位置
}
sort(a + 1, a + 1 + n, cmp);//排序
for (int i = 2; i <= n; ++i)
if (a[i].v < a[i - 1].v)//要多传一圈
ans++;
ans++;//不满一圈的
printf("%d", ans);
return 0;
}
