Как оптимизировать следующий код, поскольку он дает ошибку TLE?

Question

Викрант на фестивале в своем колледже, и, будучи настоящей едой ie, он сразу же отправился в продовольственный уголок в надежде достать деликатесы. В продовольственном уголке есть N киосков, пронумерованных от 1 до N, и в i-м киоске перед ним стоят люди Ai. Каждый киоск занимает минуту, чтобы обслужить одного человека. Викрант сначала присоединится к очереди для первого прилавка, но, будучи нетерпеливым парнем, он будет go присоединяться к очереди для следующего прилавка через каждую минуту, если его не обслуживают. (Если он стоит в очереди за последним киоском, он присоединится к тому, что касается первого киоска)

Вы должны указать продовольственный киоск, из которого будет подан Викрант. Выходные данные: Для каждого теста в новой строке выведите продовольственный киоск, который будет служить Викранту.

Ограничения: 1 ≤ T ≤ 100 1 ≤ N ≤ 105 0 ≤ Ai ≤ 106

Examples:
Input:
2
4
1 4 2 1
2
4 4
Output:
3
1

Explanation:
Testcase 1: At T = 0, he stands at stall 1, it is occupied till T=1 so he moves so stall 2, where he waits for 1 minute after which he moves to stall 3 at T = 2,
 which is empty at that point since the 2 people waiting at that stall are already serves by T = 2, so he gets serves at this stall.
Testcase 2: The progression is explained by the states given below.
4 4 T=0
3 3 T=1
2 2 T=2
1 1 T=3
0 0 T=4

#include<iostream>
using namespace std;
int main()
 {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int A[n];
        for(int i =0;i<n;i++)
            cin>>A[i];
        int T = 0;
        while(A[T] != 0)
        {
             for(int i = 0;i<n;i++)
                   A[i]--;
             T++;
             if(T>= n)
                T = T%n;

        }
        cout<<T+1<<endl;
    }
    return 0;
}

Answer 1

По сути, ваш алгоритм - O(Amax x N), где Amax - максимальное значение A[.].

Этого можно избежать, уменьшая каждое значение A только при его посещении, а не все время. Я обеспечил реализацию этой идеи. Новая сложность O(Amax + N) в худшем случае.

Однако в вашем коде также есть логическая ошибка. Эта строка:

while(A[T] != 0)

должна быть

while(A[T] > 0)

Причина в том, что это значение может стать отрицательным, просто означая, что никто больше не посещает в этом месте.

Что сбивало с толку, так это то, что эта ошибка имеет два эффекта: иногда плохие ответы, а часто и более длительное время.

#include <iostream>
#include <vector>

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> A(n);
        for (int i = 0; i < n ; ++i)
            std::cin >> A[i];
        int T = 0, i = 0;
        while (1) {
             if ((A[i] - T) <= 0) break;
             T++;
             i++;
             if (i == n) i = 0;
        }
        std::cout << i + 1 << "\n";
    }
    return 0;
}