Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 795 F. Pens And Days Of Week ( Periodic )

Problem - F - Codeforces

題意:

制約:
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;
}