CFR 795 B. Significant Cups ( Monotonicity )
題意:
你有 n 個 PhOI 獎牌,m 個 IOI 獎牌,各自用價值 c 和重量 w 描述。你有一個容器可以容下不超過 d 的總重量,問在兩種獎牌至少各一枚,且當一種獎牌中價值為 x 的獎牌被納入則所有價值超過 x 的同種獎牌也都必須納入的前提下,最大價值總和是多少。
制約:
The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 1e9) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.
Each of the following n lines contains two integers ci and wi (1 ≤ ci, wi ≤ 1e9) — significance and width of the i-th cup for Physics olympiads.
Each of the following m lines contains two integers cj and wj (1 ≤ cj, wj ≤ 1e9) — significance and width of the j-th cup for Informatics olympiads.
解法:
排序後雙指針。
時間 / 空間複雜度:
O( N + M )
var _ = readline().split( ' ' ); var N = +_[ 0 ]; // + to cast string to int var M = +_[ 1 ]; var D = +_[ 2 ]; function cmp( a, b ) { var x, y; if( a[ 0 ] != b[ 0 ] ) { x = -a[ 0 ]; y = -b[ 0 ]; } else { x = a[ 1 ]; y = b[ 1 ]; } if( x < y ) return -1; else if( x === y ) return 0; return 1; } var ACW = []; for( var i = 0; i < N; ++i ) { var __ = readline().split( ' ' ); ACW.push( [ +__[ 0 ], +__[ 1 ] ] ); } ACW.sort( cmp ); var BCW = []; for( var i = 0; i < M; ++i ) { var __ = readline().split( ' ' ); BCW.push( [ +__[ 0 ], +__[ 1 ] ] ); } BCW.sort( cmp ); var curc = 0; var curw = 0; var bptr = 0; // [ 0, bptr ) while( bptr < M ) { if( curw + BCW[ bptr ][ 1 ] > D ) break; curw += BCW[ bptr ][ 1 ]; curc += BCW[ bptr ][ 0 ]; ++bptr; } var ans = 0; for( var aptr = 0; aptr < N; ++aptr ) { curw += ACW[ aptr ][ 1 ]; curc += ACW[ aptr ][ 0 ]; while( curw > D && bptr > 0 ) { --bptr; curw -= BCW[ bptr ][ 1 ]; curc -= BCW[ bptr ][ 0 ]; } if( bptr === 0 || curw > D ) break; ans = Math.max( ans, curc ); } print( ans );