小美最近发现了一种有趣的游戏,给定一个队列q,小美会按照以下规则进行游戏:
每次从队列中取出一个数,如果这个数是当前队列中最小的值,那么小美就会丢掉这个数。否则小美就会把这个数重新加入队列。
小美会一直进行游戏直到队列变空为止,但是小美并没有多少耐心,因此她想知道她最多需要进行多少次操作才能结束游戏。
小美最近发现了一种有趣的游戏,给定一个队列q,小美会按照以下规则进行游戏:
每次从队列中取出一个数,如果这个数是当前队列中最小的值,那么小美就会丢掉这个数。否则小美就会把这个数重新加入队列。
小美会一直进行游戏直到队列变空为止,但是小美并没有多少耐心,因此她想知道她最多需要进行多少次操作才能结束游戏。
第一行一个数n表示队列中数的个数。()
第二行n个数,第i个数ai表示队列中第i个被加进去的数的值。()
输出一个值表示小美需要操作的次数。
5 6 4 2 1 3
12
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int cnt = n; vector<int> sorted(n), que(n); for (int i = 0; i < n; ++i) { int num; cin >> num; sorted[i] = que[i] = num; } sort(sorted.begin(), sorted.end(), [&](const auto& u, const auto& v) { return u < v; }); int idx = 0, start = 0; while (idx < n) { //auto it = find(que.begin() + start, que.end(), sorted[idx]); //if (it == que.end()) { // it = find(que.begin(), que.begin() + start, sorted[idx]); //} int it_idx; for (it_idx = start; it_idx < que.size(); ++it_idx) { if (que[it_idx] == sorted[idx]) { break; } } if (it_idx == que.size()) { for (it_idx = 0; it_idx < start; ++it_idx) { if (que[it_idx] == sorted[idx]) { break; } } } //cnt += (it - que.begin() + 1); //int it_idx = it - que.begin(); //if (it_idx < start) { // cnt += (n - idx - start + it_idx); //} else { // cnt += (it_idx - start); //} cnt += ((it_idx - start + (int)que.size()) % (int)que.size()); start = it_idx; que.erase(it_idx + que.begin()); //que.erase(it); ++idx; } printf("%d\n", cnt); }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n;cin>>n; vector<vector<int>> a(n,vector<int>(2)); for(int i=0;i<n;i++){ cin>>a[i][0]; a[i][1] = i; } stable_sort(a.begin(),a.end()); vector<int> dp; int pre_index = 2000000000; for(int i=0;i<n;){ int j=i,k=-1; while(j<n && a[j][0]==a[i][0]){ if(a[j][1]<pre_index) k = j; j++; } if (k==-1){ dp.back() += j-i; pre_index = a[j-1][1]; }else{ if(dp.size()) dp.back() += j-(k+1); dp.push_back(k-i+1); pre_index = a[k][1]; } i = j; } int length = dp.size(); int res = n*length--; for (auto x :dp) res -= x*length--; cout<< res; }
n = int(input()) que = list(map(int, input().split())) que_sort = sorted(que) count = 0 for a in que_sort: for i in range(len(que)): if que[i] == a: count += i+1 break que = que[i+1:] + que[:i] print(count)超时了