14010: 【原4010】谁最有耐心

题目

题目描述

author: yura 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4010

Description

终于放假了！！！作为一个热血青年，丁姐决定在假期去幼儿园做老师。

幼儿园最近很流行一种报数游戏：n个小朋友围成一圈报数，他们有各自的编号：1,2,3...n，从第一个小朋友开始依次报数。但是小朋友们不太有耐心，第i个小朋友的耐心值为Ai(Ai>1)，当他第Ai次报数以后，他就会失去耐心退出游戏;同时，他会很生气地反过来报数，以干扰其他小朋友玩游戏（例如，原来的报数顺序为顺时针，现在改为逆时针）。在其他小朋友都退出游戏以后，剩下的那一个就是最有耐心的小朋友。

丁姐想知道，最有耐心的小朋友是哪一个？

Input Format

第一行一个整数n

第二到第n+1行每行一个整数Ai，代表编号为i的小朋友的耐心值

30%数据: \(1 \leq n \leq 10 , 2 \leq Ai \leq 10 \)

80%数据: \(1 \leq n \leq 100 , 2 \leq Ai \leq 1000 \)

100%数据: \(1 \leq n \leq 1000 , 2 \leq Ai \leq 10^{6} \)

Output Format

最有耐心的小朋友的编号

Sample Input

3
4
3
3

Sample Output

3

Limits

时间限制：1000ms

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[1005], l[1005], r[1005];
void init(){
    n = read();
    REP(i, 1, n)
        l[i] = i - 1, r[i] = i + 1,
        a[i] = read();
    l[1] = n, r[n] = 1;
}
void solve(){
    int curdir = 1, cur = 1;
    REP(T, 1, n - 1){
        int mini = INF, tmp = cur;
        do{
            mini = min(mini, a[tmp]);
            tmp = (curdir ? r[tmp]: l[tmp]);
        }while (tmp != cur);
        do{
            a[tmp] -= mini - 1;
            tmp = (curdir ? r[tmp]: l[tmp]);
        }while (tmp != cur);
        for (; ; ){
            --a[cur];
            if (!a[cur]){
                if (curdir){
                    int to = l[cur];
                    r[to] = r[cur], l[r[cur]] = to;
                    cur = to;
                }else {
                    int to = r[cur];
                    l[to] = l[cur], r[l[cur]] = to;
                    cur = to;
                }
                curdir ^= 1;
                break;
            }
            cur = (curdir ? r[cur]: l[cur]);
        }
    }
    printf("%d\n", cur);
}
int main(){
    init();
    solve();
    return 0;
}