0w1

CSAcademy 23 D. Disk Mechanism ( Greedy )

Round #23 (Div. 2 only)

題意:
給若干個中心,現在你要以這些中心擺放圓。有左數起第 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;
}