CFR 795 H. Repairing Of String ( Ad hoc )

Problem - H - Codeforces

題意：
給 C[]，C[ i ] 代表長度為 i 的元素種類單一子字串的數量。求構造字串。

制約：
The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string.
The second line contains the sequence of integers c1, c2, ..., cn (0 ≤ ci ≤ 2000), where ci equals the number of substrings of the string s with the length i, consisting of the same letters.
It is guaranteed that the input data is such that the answer always exists.

解法：
考慮最大的非零 C[ i ]，顯然一定要有這麼多個長度恰為 i 的元素種類單一字串穿插，( 'a' * i ) + ( 'b' * i ) + ( 'a' * i ) ...。此時，把這些造成的貢獻減去。只要保證答案存在，那麼由 i 大至小依序做一樣的事情即可。

時間 / 空間複雜度：
O( N^2 )

import java.util.Scanner;
public class project{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] C = new int[ N + 1 ];
    for( int i = 1; i <= N; ++i ) {
      C[ i ] = sc.nextInt();  
    }
    StringBuilder ans = new StringBuilder();
    for( int i = N, t = 0; i >= 1; --i ) {
      for( int j = 0; j < C[ i ]; ++j, t ^= 1 ) {
        for( int k = 0; k < i; ++k ) {
          ans.append( ( char ) ( 'a' + t ) );
        }
      }
      for( int j = i - 1; j >= 1; --j ) {
        C[ j ] -= C[ i ] * ( i - j + 1 );
      }
    }
    System.out.println( ans );
  }
}