CSAcademy 23 D. Disk Mechanism ( Greedy )
題意:
給若干個中心,現在你要以這些中心擺放圓。有左數起第 i 個圓的半徑可以是 [ L[ i ], R[ i ] ] 中任意整數。兩個相鄰的圓必須相切。問有幾種方案。
限制:
2≤N≤1e5
The point coordinates are given in increasing order and they are integers between 0 and 10^9
The minimum and the maximum dimensions for the radius of a disk are integers between 1 and 10^9
解法:
有左到右計算,使當前以左的所有圓合法的當前這個圓的半徑範圍。顯然這個範圍是連續的,而且當前越大,右邊的圓一定不會比較小。最後所有範圍中長度最短的即為解。
時間 / 空間複雜度:
O( N )
#include <bits/stdc++.h> using namespace std; const int MAXN = ( int ) 1e5; int N; int X[ MAXN ]; int L[ MAXN ], R[ MAXN ]; signed main(){ ios::sync_with_stdio( 0 ); cin >> N; for( int i = 0; i < N; ++i ){ cin >> X[ i ]; } for( int i = 0; i < N; ++i ){ cin >> L[ i ] >> R[ i ]; } int ans = R[ 0 ] - L[ 0 ] + 1; for( int i = 1; i < N; ++i ){ int r = X[ i ] - X[ i - 1 ] - L[ i - 1 ]; int l = X[ i ] - X[ i - 1 ] - R[ i - 1 ]; if( l > R[ i ] or r < L[ i ] ){ cout << 0 << "\n"; exit( 0 ); } L[ i ] = max( L[ i ], l ); R[ i ] = min( R[ i ], r ); ans = min( ans, R[ i ] - L[ i ] + 1 ); } cout << ans << endl; return 0; }