CFR 795 F. Pens And Days Of Week ( Periodic )
題意:
制約:
The first line contains the integer n (1 ≤ n ≤ 50 000) — the number of pens Stepan has.
The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 1e9), where ai is equal to the number of milliliters of ink which the pen number i currently has.
解法:
當 N 為 7 的倍數的時候,顯然所有 i % 7 == 6 的 i 都不會拜訪到,而答案為會拜訪到的 A[ i ] 裡最小的 i。
否則,可以發現有一個週期:對所有數字減去任意適當的 6 * k,會是一樣的問題。
時間 / 空間複雜度:
O( N )
module main; import std.c.stdio; int main() { int N; scanf( "%d", &N ); int[] A = new int[ N ]; for( int i = 0; i < N; ++i ) { scanf( "%d", &A[ i ] ); } if( N % 7 == 0 ) { int minv = 0x3f3f3f3f, min_idx; for( int i = 0; i < N; ++i ) { if( i % 7 == 6 ) continue; if( minv > A[ i ] ) { minv = A[ i ]; min_idx = i; } } printf( "%d\n", min_idx + 1 ); } else { int minv = 0x3f3f3f3f; for( int i = 0; i < N; ++i ) { if( minv > A[ i ] ) { minv = A[ i ]; } } int magic = ( minv / 6 - 1 ) * 6; if( magic < 0 ) magic = 0; for( int i = 0; i < N; ++i ) { A[ i ] -= magic; } for( int i = 0, c = 0; ; i = ( i + 1 ) % N, c = ( c + 1 ) % 7 ) { if( c == 6 ) continue; if( --A[ i ] == 0 ) { printf( "%d\n", i + 1 ); break; } } } return 0; }