Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

CFR 795 B. Significant Cups ( Monotonicity )

Codeforces Monotonous javascript

Problem - B - Codeforces

題意:
你有 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 );