Jzzhu and Children CodeForces - 450A

Jzzhu and Children CodeForces - 450A

有 n 个孩子在老师的学校上学。老师决定给这些孩子一些苹果。
让我们将所有孩子编号为 1 到 n。第 i 个孩子想要获得至少 ai 的苹果。
老师叫孩子们站成一排。第 i 个孩子站在第 i 个位置上。之后老师开始分发苹果，遵循以下规则：
给第一个孩子 m 个苹果。
如果这个孩子还没获得足够的苹果，那么他走到队伍的末尾，否则就回家。
重复前两个操作直到所有孩子都回家。
老师想知道，哪个孩子会是最后一个回家的。

Input

题目含有多组数据，以下为每组数据的格式：
第一行包含两个整数 n，m (1 ≤ n ≤ 100; 1 ≤ m ≤ 100)。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 100).

Output

输出一个整数，最后回家的孩子编号。

Sample Input

5 2
1 3 1 4 2
6 4
1 1 2 2 3 3

Sample Input

4
6

分析

直接模拟一个队列

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
int n,m,a[N];

int main(){
    // freopen("data.in", "r", stdin);
    while(~scanf("%d%d", &n,&m)){
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        queue<pair<int,int> > que;
        for(int i=1; i<=n; i++) que.push(make_pair(i,a[i]));
        pair<int,int> p;
        while(que.size()){
            p = que.front(), que.pop();
            p.second -= m;
            if(p.second > 0) que.push(p);
        }
        printf("%d\n", p.first);
    }
    return 0;
}