CFR 484 B. Maximum Value ( Math, Binary Search, Harmonic Series )
題意:
給 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; }