[题解向] 带悔贪心泛做

(0x01) LG3045 [USACO12FEB]牛券

( m FJ)准备买一些新奶牛，市场上有(N)头奶牛((1leq Nleq 50000))，第(i)头奶牛价格为(P_i~(1leq P_ileq 10^9))。( m FJ)有(K)张优惠券，使用优惠券购买第(i)头奶牛时价格会降为(C_i~(1leq C_ileq P_i))，每头奶牛只能使用一次优惠券。( m FJ)想知道花不超过(M~(1leq Mleq 10^{14}))的钱最多可以买多少奶牛？

嗯，一般这种东西都是先假定一个看起来有点合理的顺序大力贪心，比如可以按照(C_i)排序去选小的。但这个贪心显然不对，比如这个样例：

K=1,N=2,M=12
P1=10,C1=1
P2=2^{63}-1,C_2=2

那就显然应该对第二个用，但贪心会去用掉第一个。所以考虑怎么反悔。观察到选完( m C_i)之后，要么选一个最小的( m P_j)，要么换出来一张优惠券去选( m C_j)。于是考虑维护两个堆，一个维护没用过Coupon的( m {P})的最小值，一个维护用过了Coupon的( m {P-C})的最小值了。

struct cows{
	int p, c, id ; 
}c[MAXN] ; 
bool vis[MAXN] ;
int N, K, ans ; LL M ;  
struct comp1{
	bool operator ()(const cows a, const cows b){ return a.c > b.c ;  }
};
struct comp2{
	bool operator ()(const cows a, const cows b){ return a.p > b.p ;  }
};
struct comp3{
	bool operator ()(const cows a, const cows b){ return a.p - a.c > b.p - b.c ;  }
};
priority_queue<cows, vector<cows>, comp1> q1 ;
priority_queue<cows, vector<cows>, comp2> q2 ;
priority_queue<cows, vector<cows>, comp3> q3 ;

int main(){
	cin >> N >> K >> M ; int i ;
	for (i = 1 ; i <= N ; ++ i){
		scanf("%d%d", &c[i].p, &c[i].c) ;
		c[i].id = i ; q1.push(c[i]), q2.push(c[i]) ; 
	}
	for (i = 1 ; i <= K ; ++ i){
		cows t = q1.top() ; q1.pop(), M -= t.c ; 
		if (M < 0) return !printf("%d
", i - 1) ;
		vis[t.id] = 1 ; q3.push(t) ; ans ++ ;
	}
	for (i = K + 1 ; i <= N ; ++ i){
		while (!q1.empty() && vis[q1.top().id]) q1.pop() ;
		while (!q2.empty() && vis[q2.top().id]) q2.pop() ; 
		if (q3.empty()){ 
			M -= q2.top().p ; if (M < 0) break ; 
			vis[q2.top().id] = 1, q2.pop() ; ++ ans ; continue ; 
		}
		int p = q2.top().p, q = q2.top().c + q3.top().p - q3.top().c ;
		if (p < q){
			M -= p ; 
			cows n = q2.top() ; q2.pop() ;
			if (M < 0) break ; ++ ans ; vis[n.id] = 1 ;
		} 
		else {
			M -= q ; 
			cows n = q1.top() ; q1.pop() ; 
			if (M < 0) break ; ++ ans ; vis[n.id] = 1 ; 
		}
	}
	cout << ans << endl ;
}

(0x02) LG1484/1792种树

给定一长度为(n)个环，环上相邻的两个位置的权值（有正有负）只能选一个，最多选(k)个位置，最大化选择的权值和。

嗯，考虑比较弱智的贪心自然是从最大的开始选，然而这么搞显然不对。于是考虑怎么去带悔贪。观察如果我们选了(i~(i>1))，那么(i-1)和(i+1)就都不能选了；而如果想要悔这一次操作，那必定是希望选(i-1)或者(i+1)（否则不用悔）。

假设现在选了(k)个，要选第(k+1)个，那么考虑把(i)扔掉之后实际上这一轮需要选两个才能保证不会出现状态转移失秩的情况；同时，当且仅当(val_{i-1}+val_{i+1}>val_i)或者(val_{i+1}>val_i)时，才会选(i+1)（不取等号是因为选了(i-1)和(i+1)如果和选(i)效果相同，那么一定会去选(i)不会更劣，否则(i-2,i+2)也不能选），前者情况已经讨论过，后者由于一开始的贪心就已经决定了(val_{i+1})会先选（即不会出现后者这种情况）。

于是就可以带悔贪心，每次合并一下即可。

namespace Greedy{
	#define ll long long
	#define Mp make_pair
	#define pr pair<ll, int>
	priority_queue <pr> q ;
	int pre[MAXN], aft[MAXN] ; ll Ans = 0 ;
	inline void Solve3(){
		for (i = 1 ; i <= N ; ++ i) 
			pre[i] = i - 1, aft[i] = i + 1, q.push(Mp(base[i], i)) ;
		aft[0] = 1, pre[N + 1] = N ;
		while (K){
			pr Now = q.top() ; q.pop() ;
			int val = Now.first, num = Now.second ;
			if (val < 0) break ; 
			if (aft[pre[num]] != num) continue ;
			base[num] = base[pre[num]] + base[aft[num]] - base[num] ;
			aft[num] = aft[aft[num]], pre[num] = pre[pre[num]] ; aft[pre[num]] = num, pre[aft[num]] = num ; 
			q.push(Mp(base[num], num)), Ans += val, K -- ; 
		}
		cout << Ans << endl ; 
	}
}

By the way，本题有一个比较显然的(dp)，设(f_{i,j})表示前(i)个元素选了(j)个的(max)，转移的时候从(f_{i-1,j})和(f_{i-2,j-1})和(f_{i-2,j})转移一下即可。

(0x03) [CTSC2007] Backup Files

……发现随手差分一下就是上一题的序列版本，于是就做完了。

。。。四倍经验可还行啊

(0x04) CF865D Buy Low Sell High

已知接下来(N)天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做。

(N)天之后你拥有的股票应为(0)。当然,希望这(N)天内能够赚足够多的钱.

考虑弱智贪心，大概就是扫一遍，遇到能买的就买，遇到价高的就卖出，最后减去多买的。但这东西显然不对。于是考虑如何反悔，发现反悔的实质就是把原来卖出的那一天换成买入。发现这样原本的差价是(y-x)，现在变成了(z-x)，那么反悔一次的获的利就是((z-x)-(y-x)=z-y)。于是拿俩堆，一个维护买入的，一个维护卖出的即可。

	for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
	for (i = 1 ; i <= N ; ++ i){
		int p = -Inf, q = -Inf, t ; 
		if (!q1.empty()) p = base[i] - q1.top() ; 
		if (!q2.empty()) q = base[i] - base[q2.top().id] ; //q2.top() = c - val
		if (p >= q){
			if (p < 0) { q1.push(base[i]) ; continue ; }
			q1.pop(), ans += p, q2.push((nd){base[i], i}) ; 
		}
		else {
			if (q < 0) { q1.push(base[i]) ; continue ; }
			nd n = q2.top() ; q2.pop() ;
			ans += q, q2.push((nd){base[i], i}), q1.push(base[n.id]) ;
		}
////		cout << ans << endl ; 
	}
	cout << ans << endl ; return 0 ;

(0x05) [JSOI2007]建筑抢修

有(n)个建筑，修理工人修理完一个建筑才能修理下一个建筑，且不能同时修理多个建筑。每个建筑有一个(t_i)修建该建筑需要用的时间，(e_i)表示报废的时间。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。制订一个修理顺序，以抢修尽可能多的建筑。

(nleq 2e5)

由于没有起始时间的限制，于是可以乱搞。考虑按照(e)排序，从前往后选，遇到一个新的时，考虑怎么反悔——反悔=之前的不修，那么如果发现之前修的里面有用时比现在这个大的，那肯定是修现在这个更合适，于是反悔一下即可。

bool comp(Bds a, Bds b){ return a.c < b.c ; }
int main(){
	cin >> N ; int t = 0, i ;
	for (i = 1 ; i <= N ; ++ i) 
		scanf("%d%d", &base[i].s, &base[i].c) ; 
	sort(base + 1, base + N + 1, comp) ;
	for (i = 1 ; i <= N ; ++ i){
		if (t + base[i].s <= base[i].c){
			q.push(base[i].s) ; 
			++ ans ; t += base[i].s ; continue ;
		}
		else if (!q.empty()){
			int tmp = q.top() ;
			if (tmp > base[i].s)
				q.pop(), q.push(base[i].s), t += -tmp + base[i].s ;
 		}
	}
	cout << ans << endl ; return 0 ;
}