Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 798 D. Mike and distribution ( Adhoc / Random )

Problem - D - Codeforces

題意:
給長度 N 的兩個數列 A, B,求構造一個 C[],使得 len( C ) ≤ N / 2 + 1,且所有元素相異,且任意 i 滿足 1 ≤ C[ i ] ≤ N,並有 sum( A[ k ] for k in C ) * 2 > sum( A ) 且 sum( B[ k ] for k in C ) * 2 > sum( B )。

制約:
The first line contains integer n (1 ≤ n ≤ 1e5) — the number of elements in the sequences.
On the second line there are n space-separated integers a1, ..., an (1 ≤ ai ≤ 1e9) — elements of sequence A.
On the third line there are also n space-separated integers b1, ..., bn (1 ≤ bi ≤ 1e9) — elements of sequence B.

解法:
變換條件,觀察其實要取一個子集合,使得該價值總和超過該子集合外的元素的價值總和。
考慮 C[ i ] = pair( A[ i ], B[ i ] ),並對 C 排序使 first 非遞增。
取越多越好,所以考慮取恰好 N // 2 + 1 個。
考慮每相鄰兩個元素取一個。這麼取可以有多一個元素的空閑,所以第一個元素直接取,後面再兩兩進行決策。
結論是,對於任一一對這樣的決策,總是取 second 比較大的一定不會丟失解。
首先顯然對於 B,一定滿足條件。
至於 A,注意到已經額外的取得了 A 中最大值。條件等價,取得的總和 - 沒取得的總和 > 0。考慮數線,沒取得的總和是相鄰兩個點的距離的總和,顯然這個總和至多是最大值 - 1。

時間 / 空間複雜度:
O( N )

from functools import cmp_to_key

N = int( input() )
A = list( map( int, input().split() ) )
B = list( map( int, input().split() ) )

ord = sorted( list( i for i in range( N ) ), key = cmp_to_key( lambda x, y: A[ y ] - A[ x ] ) )

ans = [ ord[ 0 ] ]
for i in range( 1, N, 2 ):
  if i + 1 == N:
    ans.append( ord[ i ] )
  else:
    if B[ ord[ i ] ] >= B[ ord[ i + 1 ] ]:
      ans.append( ord[ i ] )
    else:
      ans.append( ord[ i + 1 ] )

print( len( ans ) )
print( *list( map( lambda x: x + 1, ans ) ) )

另解:
random_shuffle()
f:id:h0rnet:20170423213453p:plain

import random
import datetime

random.seed( datetime.datetime.now() )
N = int( input() )
A = list( map( int, input().split() ) )
B = list( map( int, input().split() ) )

def valid( arr ):
  return sum( A[ k ] for k in arr ) * 2 > sum( A ) and sum( B[ k ] for k in arr ) * 2 > sum( B )

ans = [ i for i in range( N ) ]
while not valid( ans[ : N // 2 + 1 ] ):
  random.shuffle( ans )

print( N // 2 + 1 )
print( *list( map( lambda x: x + 1, ans[ : N // 2 + 1 ] ) ) )