簽訂協議

nowcoder 217601

題目大意

給出n個數，現在有一個協議書，讓你從1傳到n，然后傳回1，繼續傳下去
對于第i個數，如果前面i-1個數已經匹配過了，那么當協議書傳過來時即可匹配，否則無法匹配
我讓你讓所有數匹配最少傳多少圈（向上取整）

輸入樣例#1

5 1 5 8 4 3

輸出樣例#1

3

輸入樣例#2

10 11 8 5 7 1 6 2 3 4 10

輸出樣例#2

6

樣例解釋#1

第一輪：8
第二輪：5 4 3
第三輪：1

數據范圍

$$\begin{gathered} 1?n?8\times 10^5 \\ 1?a_i?10^6 \end{gathered}$$

解題思路

如果直接暴力枚舉會TLE
當匹配完值為$i$的點后需要匹配值為$i+1$的點
那么可以按$a_i$排序，這樣得到匹配的數的順序
設$v_i$為當前數的初始位置
如果$v_i>v_{i?1}$那么不用多傳一圈
否則要多傳一圈

代碼

#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; }

總結

以上是生活随笔為你收集整理的【模拟】签订协议（nowcoder 217601）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。