CFR 738 C. Road to Cinema ( Binary Search )

Problem - C - Codeforces

題意：
給很多車，用價格和油箱容量描述。給加油站，用位置描述。過加油站時油箱會免費加滿油。起點 0 終點 S，求最便宜的車，可以不超過 T 分鐘到達終點。對每一單位距離都有兩種移動方式，用一單位的油兩分鐘過，或用兩單位的油一分鐘過。

資料規模：
n: 車的數量, k: 加油站數量, s: 終點, t: 目標時間
1 ≤ n ≤ 2e5, 1 ≤ k ≤ 2e5, 2 ≤ s ≤ 1e9, 1 ≤ t ≤ 2e9
ci: 第 i 個車的價格, vi: 第 i 個車的油箱容量
1 ≤ ci, vi ≤ 1e9
gi: 第 i 個加油站位置
1 ≤ gi ≤ s - 1
時限 1000 ms
記憶體 256 MB

解法：
如果有個車的價格比另某一台貴，油箱容量卻沒有比較大，就是完全不值得考慮的。將完全不值得考慮的車都除去之後，可選的車會形成對價格和油箱容量兩者都嚴格遞增的序列。此時已有單調性，因此對價格二分搜即得解。
但其實只要先對容量二分搜後，再線性掃一次所有車會比較好寫。

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

需要注意：
第 27 行，千萬不能寫成 if( CV[ i ].second > CV[ i - 1 ].second )

int N, K, S, T;
vp CV;
vi G;

void init(){
	cin >> N >> K >> S >> T;
	CV = vp( N );
	for( int i = 0; i < N; ++i )
		cin >> CV[ i ].first >> CV[ i ].second;
	G = vi( K );
	for( int i = 0; i < K; ++i )
		cin >> G[ i ];
}

vp cv;

bool cmp( const pii a, const pii b ){
	if( a.first != b.first )
		return a.first < b.first;
	return a.second > b.second;
}

void preprocess(){
	sort( CV.begin(), CV.end(), cmp );
	cv.emplace_back( CV[ 0 ] );
	for( int i = 1; i < N; ++i )
		if( CV[ i ].second > cv.back().second )
			cv.emplace_back( CV[ i ] );
	sort( G.begin(), G.end() );
}

int ok( int x ){
	int t = 0;
	int lp = 0;
	for( int i = 0; i < G.size(); ++i ){ // gas - 2a ≥ d - a, gas - d ≥ a
		int d = G[ i ] - lp;
		if( cv[ x ].second < d )
			return 0;
		int a = min( d, ( cv[ x ].second - d ) );
		int b = d - a;
		t += a + 2 * b;
		lp = G[ i ];
	}
	int d = S - G.back();
	if( cv[ x ].second < d )
		return 0;
	int a = min( d, ( cv[ x ].second - d ) );
	int b = d - a;
	t += a + 2 * b;
	return t <= T;
}

void solve(){
	for( int i = 1; i < cv.size(); ++i )
		assert( cv[ i ].first > cv[ i - 1 ].first and cv[ i ].second > cv[ i - 1 ].second );
	int ans = -1;
	int lb = 0, rb = cv.size() - 1;
	while( lb <= rb ){
		int mid = lb + rb >> 1;
		if( ok( mid ) )
			ans = mid, rb = mid - 1;
		else
			lb = mid + 1;
	}
	if( ans == -1 )
		cout << -1 << endl;
	else
		cout << cv[ ans ].first << endl;
}