「ROI 2019 Day2」课桌

题目

分析

分析一下性质：

如果某一类桌子的覆盖范围被其它桌子包含，那么这类桌子是没用的。
在一个班里，必然是从小到大排序后的相邻两个人坐一张桌子。
在 (m) 个班中，必然是从小到大排序后排名相同的一对人坐同一张桌子。

说明：比如 (m) 个班中都是最矮的一对坐最矮的桌子（意思是第 (i) 高的一对都是坐第 (i) 高的桌子）。
桌子高度按照人的高度单调。

说明：当 (i<j) 时，第 (i) 高的人的桌子不可能高于第 (j) 高的人的桌子。

第一条性质非常显然，第二三四条都可以通过尝试交换来验证。

注意一下最后一条性质，这说明了决策存在单调性。当我们找到了第 (i) 高的人的桌子之后，我们就知道了比他们矮的人的桌子的范围，也知道了比他们高的人的桌子的范围。

因此我们可以采用分治方法。用 (([l,r],[L,R])) 来表示正在对 ([l,r]) 的人分配 ([L,R]) 的桌子。那么我们就可以取出 ([l,r]) 中点 (M) ，枚举 (M) 的最优桌子 (k) ，并且分治到 (([l,M),[L,K])) 和 (((M,r],[K,R])) 。

时间可以做到 (O(klog_2{mn})) 。

小结：

对于单调性和分治方法的利用比较巧妙。~~人菜吧，不太会分治~~

代码

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;
typedef pair<int, int> Seg;

const LL INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 4e5 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

vector<int> pnt[MAXN];

int H[MAXN]; LL su[MAXN];
Seg desk[MAXN];
int M, N, K;

LL Divide( const int l, const int r, const int L, const int R )
{
	if( l > r || L > R ) return 0;
	LL ret = INF, tmp;
	int m = l + r >> 1, ind = -1, lim = ( M << 1 ) - 1; 

	rep( i, 0, lim ) su[i] = ( i ? su[i - 1] : 0 ) + pnt[m][i];
	for( int i = L, pl = -1, pr = -1 ; i <= R ; i ++ )
	{
		while( pl < lim && pnt[m][pl + 1] < desk[i].first ) pl ++;
		while( pr < lim && pnt[m][pr + 1] <= desk[i].second ) pr ++;
		tmp = su[lim] - ( ~ pr ? su[pr] : 0 ) - 1ll * desk[i].second * ( lim - pr );
		if( ~ pl ) tmp += 1ll * desk[i].first * ( pl + 1 ) - su[pl];
		if( ret > tmp ) ind = i, ret = tmp;
	}
	return ret + Divide( l, m - 1, L, ind ) + Divide( m + 1, r, ind, R );
}

int main()
{
	read( M ), read( N ), read( K );
	rep( i, 1, K ) read( desk[i].first ), read( desk[i].second );
	rep( i, 1, M )
	{
		rep( j, 1, N << 1 ) read( H[j] );
		sort( H + 1, H + 1 + ( N << 1 ) );
		for( int j = 1 ; j <= N << 1 ; j += 2 )
			pnt[j + 1 >> 1].push_back( H[j] ),
			pnt[j + 1 >> 1].push_back( H[j + 1] );
	}
	rep( i, 1, N ) 
		sort( pnt[i].begin(), pnt[i].end() );
	
	int tot = 0;
	sort( desk + 1, desk + 1 + K );
	rep( i, 1, K ) if( ! tot || desk[i].second > desk[tot].second )
		desk[++ tot] = desk[i];
	K = tot;
	
	write( Divide( 1, N, 1, K ) ), putchar( '
' );
	return 0;
}