0w1

CFR 484 B. Maximum Value ( Math, Binary Search, Harmonic Series )

Problem - 484B - Codeforces

題意:
給 N 個數字的數列 A。求最大的 A[ j ] % A[ i ],滿足 A[ j ] ≥ A[ i ]。

資料規模:
N ≤ 2e5
max{ A } ≤ 1e6

解法:
首先發現相同的值是沒有用的,所以 unique() 一下。此時就能因為 Harmonic Series 想到每個數的倍數數量總和不超過 max{ A } lg max{ A }。因此只要對所有 A[ i ] 分別枚舉倍數 x,再二分搜出 A 數列中比 x 小的最大值,便不會漏掉所求最大值。

時間 / 空間複雜度:
O( max{ A } lg max{ A } lg N ) / O( N )

領悟:
先將沒必要的東西分清楚,刪減後,也許題目會簡化許多。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;

int N;
int A[ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  sort( A, A + N );
  N = unique( A, A + N ) - A;
  int ans = 0;
  for( int i = 0; i < N; ++i ){
    for( int j = A[ i ] * 2; j <= ( int ) 2e6; j += A[ i ] ){
      int r = lower_bound( A, A + N, j ) - A;
      if( r - 1 < 0 ) continue;
      ans = max( ans, A[ r - 1 ] % A[ i ] );
    }
  }
  cout << ans << endl;
  return 0;
}