codeforces Least Cost Bracket Sequence

本文从WordPress迁移而来, 查看全部WordPress迁移文章

贪心（在保证一个限制条件下贪心，贪心用一个堆来维护）

http://codeforces.com/problemset/problem/3/D

题意：略

这题是选拔赛又纠结了一个下午，一直想用dp但是不行，到最后才想到用贪心，但是最后还是没有把贪心策略想出来，看了题解理解出来的

  1. 如果是一个没有问题的括号串要怎么判断是否是个合法的匹配？一般的方法是用栈，如果中途出现了’)’但是栈中空，那么就失败了。或者所有括号读完了，栈中还有元素，那么也是失败的。其实我们可以只用一个计数器来代替栈，效果完全一样。count计数器，遇到’(‘增1，遇到’)’减1，如果串还没读完count出现了小于0的值，那么和栈的第一种情况是等价的，失败。如果读完了整个串，count不为0（那只会为正数），那么和栈的第二种情况是等价的
  2. 贪心的前提是一定要保证这个问题有解。一开始将所有’?’换成’)’，然后先计算一个花费
    1. 替换完后从左到右读这个串，从上面说的方法去计数
    2. 如果读到’(‘，那么这个’(‘原来一定不是括号，并且count++
    3. 如果读到’)’，count–，但是要判断这个’)’是不是由’?’变来的，如果是的话，将这个元素放入一个堆中，堆中的每个元素要记录两个信息，一个信息就是它来自于串中的那个位置，另一个信息等下再说
    4. 如果count<0，说明出现了无法匹配的情况，但这时候不是退出宣布失败，而是看看能不能补救，之所以会发生不匹配，可能是因为一开始的时候将所有’?’变成了’)’导致的，也就是说看看之前是否出现过’?’，如果没有出现过，那么说明这个不匹配是不关’?’的事的，那么只好退出宣告失败了。但是如果之前出现了’?’，那么还可以补救，那么就将前面的’?’换成’(‘,就可以抵消掉当前这个’)’.但是前面可能有多个’?’，要怎么选？贪心就是贪在这里。

试想，一开始将所有’?’变为’)’并计算了花费 +b，现在把一个’)’变回’(‘，那么花费的变化就是 cost - b + a = cost + (a-b) , 也就是说要让cost越小，让(a-b)越小。所以之前堆记录的另外一个信息就是每个括号的a-b值，每次从推堆中取出一个’?’就是取出a-b值最小的那个元素。

取出一个’?’将其从’)’变为’(‘的时候，会对count值产生影响，本来是’)’变’(‘，count += 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 50010
#define INF 0x3f3f3f3f
#define ll long long
#define cl memset

ll ans;
int n,m;
char str[N];
int val[N];
struct elem{
	int val;
	int index;
	elem(int __val,int __index){
		val = __val; index = __index;
	}
	bool operator<(struct elem x) const{
		return x.val < val;
	}
};
priority_queue<elem>heap;

int main(){
	while(scanf("%s",str)!=EOF){
		m = ans = 0;
		cl(val,0x3f,sizeof(val));
		while(!heap.empty()) heap.pop();
		for(int i = 0; str[i]; i++)
			if(str[i] == '?'){
				int a,b;
				scanf("%d%d",&a,&b);
				ans += b; val[i] = a-b; str[i] = ')';
			}
		int Count = 0;
		for(int i = 0; str[i]; i++){
			if(str[i] == '(') Count++;
			else{
				Count--;
				if(val[i] != INF)
					heap.push(elem(val[i],i));
				if(Count < 0){
					if(heap.empty()) break;
					elem now = heap.top();
					heap.pop();
					ans += now.val;
					str[now.index] = '(';
					Count += 2;
				}
			}
		}
		if(Count == 0){
			cout << ans << endl;
			printf("%s\n",str);
		}
		else puts("-1");
	}
	return 0;
}