Educational Codeforces Round 76 (Rated for Div. 2) E. The Contest

Educational Codeforces Round 76 (Rated for Div. 2) E. The Contest（dp+线段树）

题目链接

题意：

给定3个人互不相同的多个数字，可以把数字移动给别人，问最少移动几次后可以使第一个人的数字为1 _{m1,第二个人m1} m2,第三个人m2~n（可以没有数字）

题解：

设c[1][i]为第一个人m1为i时需要移动的次数，c[3][i]为m2为i是第三个人需要操作的次数，当其他两个人数字合法时，第二个人的数字也会合法.枚举第一个人的每个i,查询m2为（i+1~n+1）的最小操作次数，ans = min{c[1][i]+min(c[3]k)} 查询操作可用线段树维护

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 250000;

int t[4*N],a[5][N],b[5][N],c[5][N];

void build(int x,int l,int r)

{

	if (l == r)

	{

		t[x] = c[3][l];

		return;

	}

	int mid = (l + r) >>1;

	build(x<<1,l,mid);

	build(x<<1|1,mid+1,r);

	t[x] = min(t[x<<1] , t[x<<1|1]);

}

int query(int x,int l,int r,int ll,int rr)

{

	if (ll <= l && r <= rr) return t[x];

	int mid = (l + r) >> 1;

	int ans = 1<<30;

	if (ll <= mid) ans = min(ans,query(x<<1,l,mid,ll,rr));

	if (rr > mid ) ans = min(ans,query(x<<1|1,mid+1,r,ll,rr));

	return ans;

}

int main()

{

	int k1,k2,k3;

	cin >> k1 >> k2 >> k3;

	int n = k1+k2+k3;

	memset(b,0,sizeof(b));

	memset(c,0,sizeof(c));

	for (int i = 1; i <= k1; i++)

	{

		cin >> a[1][i];

		b[1][a[1][i]] = 1;

	}

	for (int i = 1; i <= k2; i++) cin >> a[2][i];

	for (int i = 1; i <= k3; i++)

	{

		cin >> a[3][i];

		b[3][a[3][i]] = 1;

	}

	c[1][0] = k1;

	for (int i = 1; i <= n; i++)

	{

		b[1][i] = b[1][i-1]+b[1][i]; //记录第一个人前i个数中拥有几个

		c[1][i] = i - b[1][i] + k1 - b[1][i];//i-b[1][i]为需要移动到第一个人的操作数，k1-b[1][i]为第一个人把数移动出去的操作数

	}

	c[3][n+1] = k3;

	for (int i = n; i; i--)

	{

		b[3][i] = b[3][i+1] + b[3][i];

		c[3][i] = n-i+1-b[3][i] +k3 - b[3][i]-(k1-b[1][i-1]); //如果是第一个人可以移动到第三个人的数会重复需要减掉

	}

	for (int i = 1; i < n; i++)

	 c[1][i] -= k3-b[3][i+1];//第三个人可以移动到第一个人的数

	build(1,0,n+1);

	int ans = c[1][n];

	for (int i = 0; i < n; i++)

	{

		ans = min(ans, c[1][i] + query(1,0,n,i+1,n+1));

	}

	cout << ans << endl;

}