循环队列版题解

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
int n;
 
inline void solve()
{
    int n;
    scanf ("%lld" , &n);
    queue<pair<int , int > > q;
    for (int i = 1 ; i <= n ; i ++ )
    {
        pair<int , int > temp;
 
        scanf("%lld" , &temp.first);
        temp.second = i;
 
        q.push(temp);
    }
      
    int num = 1;
    int king = 1;
    int m = q.front().first;
    while(!q.empty())
    {
        if (num == m)
        {
            if (king == n) 
            {
                printf ("%lld" , q.front().second);
                return ;
            }
            q.pop();
            num = 1;
            king ++;
            m = q.front().first;
        }
        else
        {
            q.push(q.front());
            q.pop();
            num ++;
        }
    }
    cout << endl;
      
}
 
signed main()
{   
    solve();
    return 0;
}

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N =  5 *1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int n;
int a[N],q[N];
inline void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int hh = 0 , tt = -1;
    for(int i=1;i<=n;i++) q[++tt] = i; 
    int m = a[1] , cnt = 1 , ans;
    while(hh<=tt)
    {
        if(cnt > n) break;
        int t = q[hh++];
        if(cnt == m)
        {
            cnt = 1;
            m = a[q[hh]];
            ans = t;
        }
        else
        {
            cnt ++;
            q[++tt] = t;
        }
    }
    printf("%d",ans);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    // int _; cin>>_; while(_--){}
    solve();
    return 0;
}

参考答案：

#include <iostream>
#include <list>
using namespace std;

int main()
{
    int n;
    cin >> n;

    list<pair<int, int>> L;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        L.push_back({ i, x });
    }

    auto it = L.begin();
    while (L.size() > 1)
    {
        int cnt = it->second;


        for (int i = 1; i < cnt; i++) 
        {
            it++;
            if (it == L.end()) it = L.begin();
        }


        it = L.erase(it);
        if (it == L.end()) it = L.begin();
    }

    cout << L.front().first << endl;

    return 0;
}

#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define PII pair<int,int>
using namespace std;
const int N =  1 *1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n;
int a[N];
queue<int> q;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) q.push(i);
    int cnt = 1,m = a[1],ans=0;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        if(cnt==m)
        {
            cnt = 1;
            if(!q.empty()) m = a[q.front()];
            ans = t;
            continue;
        }
        cnt++;
        q.push(t);
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--){solve();}
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.08 19:18:52
 */