CFR 795 A. Amusement Park ( Greedy, Ternary Search )

Problem - A - Codeforces

題意：
有 N 個人，用一個 01 序列描述，0 代表小孩，1 代表大人。給定 C1, C2，你要將這些人分群，使得每個群至少有一個大人，而且最小化 sum( C1 + C2 * ( X[ i ] - 1 )^2 )，其中 X[ i ] 代表第 i 個群的人數。

制約：
The first line contains three integers n, c1 and c2 (1 ≤ n ≤ 200 000, 1 ≤ c1, c2 ≤ 1e7) — the number of visitors and parameters for determining the ticket prices for a group. The second line contains the string of length n, which consists of zeros and ones. If the i-th symbol of the string is zero, then the i-th visitor is a pupil, otherwise the i-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils.

解法：
注意到，如果決定好要分成 g 個群，那麼這些群中大小最大的和最小的差越小越好。因此只要決定要分成幾個群，最佳的分法是唯一確定的。另外，這是二次函數的圖形，所以無聊可以套個三分搜。

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

#include <stdio.h>
#include <assert.h>

int N, C1, C2;
char seq[ ( int ) 2e5 ];
int adult, child;

long long sqr( int x ) {
  return 1LL * x * x;
}

long long calc( int g ) {
  int ln = N / g; // number of people in less group
  int lc = g - N % g; // number of groups of less people
  int gn = ln + 1;
  int gc = N % g;
  return ( sqr( ln - 1 ) * C2 + C1 ) * lc + ( sqr( gn - 1 ) * C2 + C1 ) * gc;
}

signed main() {
  scanf( "%d %d %d", &N, &C1, &C2 );
  scanf( "%s", seq );
  for( int i = 0; i < N; ++i ) {
    if( seq[ i ] == '1' ) {
      ++adult;
    } else {
      ++child;
    }
  }
  int lb = 1, ub = adult;
  while( ub - lb > 10 ) {
    int x = lb + ( ub - lb ) / 3;
    int y = lb + ( ub - lb ) * 2 / 3;
    long long a = calc( lb ), b = calc( x ), c = calc( y ), d = calc( ub );
    if( a <= b && b <= c && c <= d ) {
      ub = x;
    } else if( a >= b && b <= c && c <= d ) {
      ub = y;
    } else if( a >= b && b >= c && c <= d ) {
      lb = x;
    } else if( a >= b && b >= c && c >= d ) {
      lb = y;
    } else {
      assert( 0 );
    }
  }
  long long ans = 1LL << 60;
  for( int i = lb; i <= ub; ++i ) {
    long long t = calc( i );
    if( ans > t ) {
      ans = t;
    }
  }
  printf( "%lld\n", ans );
  return 0;
}