F. New Year and Rainbow Roads

GoodBye2017 F题。

最后一分钟被绝杀，被手速坑了。。。

容易发现，R，B都必须与G相连，分下面三种情况

1.对于在最左边G的左边的点，一定会连这个G

2.那么也就是在某两个G中间，求得如何连接使得两个黑点（经过R，B ）花费最小

3.对于在最右边G的右边的点，一定会连这个G

1 3 很简单，考虑2，有下面几种情况：

1.两个G中间没有RB，那么连接两个G就好了。

2.两个G中间有R，那么必须连接两个G，然后把R分为两段，左边的一段与左边的G相连，右边的一段与右边的G相连。

3.两个G中间有B，与2同理

4.两个G中间有B R，那么可以把区间里的B和R分别串在一起，再与G相连，或者像上面那样找出分割点，然后分别与G相连，那么求得这两个值得最小值就好了。

另外，还要特判没有G得情况，直接就是RB得链长和

c++代码如下：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cctype>
#include<set>
#include<string>
#include<iostream>
#include<algorithm>
#include<string>
#define eps 1e-9
#define mp make_pair
#define lowbit(x) (x & (-x))
#define random(l,r) (rand()%(r - l + 1) + l)
#define size(a) ((int) a.size())
#define rep(i,x,y) for(register int i = x;i <= y;++i)
#define repd(i,x,y) for(register int i = x;i >= y;--i)
using namespace std;
typedef long long ll;
template<typename T>void read(T&x)
{
	x = 0;char c;int sign = 1;
	do { c = getchar();if(c == '-') sign = -1; }while(!isdigit(c));
	do { x = x * 10 + c - '0'; c = getchar();	}while(isdigit(c));
	x *= sign;
}

const int N = 3e5 + 500;
int n,cnt;ll ans;
char c;
struct Str
{
	ll pos;
	int k;
 } num[N];

int main()
{
	read(n);
	rep(i,1,n)
	{
		read(num[++cnt].pos);
		
		do { c = getchar(); }while(c != 'G' && c != 'B' && c != 'R');
		if(c == 'G') num[cnt].k = 1;
		else if(c == 'B') num[cnt].k = 2;
		else if(c == 'R') num[cnt].k = 3;
	}

	int l=0,r=0;
	rep(i,1,cnt) if(num[i].k == 1) { l = i;break; }
	repd(i,cnt,1) if(num[i].k == 1) { r = i;break; }
	if(l == r && r == 0)
	{
		rep(i,1,cnt) if(num[i].k == 2) { l = i;break; }
		repd(i,cnt,1) if(num[i].k == 2) { r = i;break; }
		ans = num[r].pos - num[l].pos;
		l = 0,r = 0;
		rep(i,1,cnt) if(num[i].k == 3) { l = i;break; }
		repd(i,cnt,1) if(num[i].k == 3) { r = i;break; }
		
		ans += num[r].pos - num[l].pos;
		printf("%I64d\n",ans);
		return 0;
	}
	rep(i,1,l - 1) if(num[i].k == 2) { ans += num[l].pos - num[i].pos;break; }
	rep(i,1,l - 1) if(num[i].k == 3) { ans += num[l].pos - num[i].pos;break; }
	repd(i,cnt,r + 1) if(num[i].k == 2) { ans += num[i].pos - num[r].pos; break; }
	repd(i,cnt,r + 1) if(num[i].k == 3) { ans += num[i].pos - num[r].pos; break; }
	rep(i,l,r)
	{
		int j = i + 1;
		while(num[j].k != 1 && j <= r) ++j;
		if(j > r) break;
		ll p1 = 0,p2 = 0,lst1 = i,lst2 = i;
		bool e1 = 0,e2;
		rep(q,i + 1,j)
			if(num[q].k == 2) e1 = 1,p1 = max(p1,num[q].pos - num[lst1].pos),lst1 = q;
			else if(num[q].k == 3) e2 = 1,p2 = max(p2,num[q].pos - num[lst2].pos),lst2 = q;
		if(e1 || e2) ans += min((e1?(num[j].pos - num[i].pos - max(p1,num[j].pos - num[lst1].pos)) : 0)+
			(e2?(num[j].pos - num[i].pos - max(p2,num[j].pos - num[lst2].pos)) : 0) + (num[j].pos - num[i].pos)
			, 2 * (num[j].pos - num[i].pos));
		else ans += num[j].pos - num[i].pos;
		i = j - 1;
	}
	
	cout << ans <<endl;
	
	return 0;
}

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<cctype>

#include<set>

#include<string>

#include<iostream>

#include<algorithm>

#include<string>

#define eps 1e-9

#define mp make_pair

#define lowbit(x) (x & (-x))

#define random(l,r) (rand()%(r - l + 1) + l)

#define size(a) ((int) a.size())

#define rep(i,x,y) for(register int i = x;i <= y;++i)

#define repd(i,x,y) for(register int i = x;i >= y;--i)

using namespace std;

typedef long long ll;

template<typename T>void read(T&x)

{

x = 0;char c;int sign = 1;

do { c = getchar();if(c == '-') sign = -1; }while(!isdigit(c));

do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));

x *= sign;

}

const int N = 3e5 + 500;

int n,cnt;ll ans;

char c;

struct Str

{

ll pos;

int k;

} num[N];

int main()

{

read(n);

rep(i,1,n)

{

read(num[++cnt].pos);

do { c = getchar(); }while(c != 'G' && c != 'B' && c != 'R');

if(c == 'G') num[cnt].k = 1;

else if(c == 'B') num[cnt].k = 2;

else if(c == 'R') num[cnt].k = 3;

}

int l=0,r=0;

rep(i,1,cnt) if(num[i].k == 1) { l = i;break; }

repd(i,cnt,1) if(num[i].k == 1) { r = i;break; }

if(l == r && r == 0)

{

rep(i,1,cnt) if(num[i].k == 2) { l = i;break; }

repd(i,cnt,1) if(num[i].k == 2) { r = i;break; }

ans = num[r].pos - num[l].pos;

l = 0,r = 0;

rep(i,1,cnt) if(num[i].k == 3) { l = i;break; }

repd(i,cnt,1) if(num[i].k == 3) { r = i;break; }

ans += num[r].pos - num[l].pos;

printf("%I64d\n",ans);

return 0;

}

rep(i,1,l - 1) if(num[i].k == 2) { ans += num[l].pos - num[i].pos;break; }

rep(i,1,l - 1) if(num[i].k == 3) { ans += num[l].pos - num[i].pos;break; }

repd(i,cnt,r + 1) if(num[i].k == 2) { ans += num[i].pos - num[r].pos; break; }

repd(i,cnt,r + 1) if(num[i].k == 3) { ans += num[i].pos - num[r].pos; break; }

rep(i,l,r)

{

int j = i + 1;

while(num[j].k != 1 && j <= r) ++j;

if(j > r) break;

ll p1 = 0,p2 = 0,lst1 = i,lst2 = i;

bool e1 = 0,e2;

rep(q,i + 1,j)

if(num[q].k == 2) e1 = 1,p1 = max(p1,num[q].pos - num[lst1].pos),lst1 = q;

else if(num[q].k == 3) e2 = 1,p2 = max(p2,num[q].pos - num[lst2].pos),lst2 = q;

if(e1 || e2) ans += min((e1?(num[j].pos - num[i].pos - max(p1,num[j].pos - num[lst1].pos)) : 0)+

(e2?(num[j].pos - num[i].pos - max(p2,num[j].pos - num[lst2].pos)) : 0) + (num[j].pos - num[i].pos)

, 2 * (num[j].pos - num[i].pos));

else ans += num[j].pos - num[i].pos;

i = j - 1;

}

cout << ans <<endl;

return 0;

}

2017年12月30日 424 0 /

codeforces

Tag: 贪心法