文章目錄

• [JSOI2007]建筑搶修
• [USACO12FEB]Cow Coupons G
• CF1251E2 Voting (Hard Version)
• CF436E Cardboard Box

[JSOI2007]建筑搶修

luogu4053

將建筑按照結束時間從小到大排序

然后記錄一下已經修理的建筑總共的花費時間

如果花費時間加上現在這個建筑的修建時間超過了這個建筑的結束時間

就考慮反悔最長修建時間的建筑（必須要比現在的這個建筑修建時間長才行）

用大根堆維護即可

如果沒有比現在這個建筑更長時間的已修建的建筑，那么這個建筑就無法被修建

這個貪心的原理是：建筑之間沒有權值，換言之修建任何一個建筑的收益是等價的，那么排序后就盡可能地騰出更多的空閑時間給后面的建筑修建

#include <queue> #include <cstdio> #include <algorithm> using namespace std; #define int long long #define maxn 150005 struct node { int ti, lim; }v[maxn]; priority_queue < int > q; int n;signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ )scanf( "%lld %lld", &v[i].ti, &v[i].lim );sort( v + 1, v + n + 1, []( node x, node y ) { return x.lim < y.lim; } );int now = 0, ans = 0;for( int i = 1;i <= n;i ++ ) {if( now + v[i].ti <= v[i].lim )now += v[i].ti, q.push( v[i].ti ), ans ++;else {if( ! q.empty() and q.top() > v[i].ti )now -= q.top(), now += v[i].ti, q.pop(), q.push( v[i].ti );}}printf( "%lld\n", ans );return 0; }

[USACO12FEB]Cow Coupons G

luogu3045

按每頭牛的打折后的c從小到大排序

考慮前$k$頭牛肯定是都把優惠券用了，然后進入反悔堆，p-c

而后考慮兩種情況

• 不用優惠券，就是原價購買，這需要對第$k$頭牛后面的所有牛進行原價的排序，用小根堆維護
• 用優惠券，反悔一張效果最差的（也就是p-c最小的）加上這頭牛打折后的價格，就是反悔后的花費

兩個取較小值與現在的金額比較即可

#include <queue> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 500005 #define int long long #define Pair pair < int, int > #define inf 1e18 priority_queue < int, vector < int >, greater < int > > q; priority_queue < Pair, vector < Pair >, greater < Pair > > q1, q2; struct node { int p, c; }cow[maxn]; int n, m, k; bool vis[maxn];signed main() {scanf( "%lld %lld %lld", &n, &k, &m ); for( int i = 1;i <= n;i ++ ) scanf( "%lld %lld", &cow[i].p, &cow[i].c );sort( cow + 1, cow + n + 1, []( node x, node y ) { return x.c < y.c; } );for( int i = 1;i <= k;i ++ ) {if( cow[i].c <= m ) m -= cow[i].c, q.push( cow[i].p - cow[i].c );else return ! printf( "%lld\n", i - 1 );}if( k == n ) return ! printf( "%lld\n", n );int ans = k;for( int i = k + 1;i <= n;i ++ ) {q1.push( make_pair( cow[i].c, i ) );q2.push( make_pair( cow[i].p, i ) );}q.push( inf );q1.push( make_pair( inf, 0 ) );q2.push( make_pair( inf, 0 ) );while( 1 ) {while( vis[q1.top().second] ) q1.pop(); while( vis[q2.top().second] ) q2.pop();int i1 = q1.top().second;int i2 = q2.top().second;int w1 = q.top() + q1.top().first;int w2 = q2.top().first;if( min( w1, w2 ) > m ) break;ans ++; m -= min( w1, w2 );if( w1 < w2 )q.pop(), q1.pop(), vis[i1] = 1, q.push( cow[i1].p - cow[i1].c );elseq2.pop(), vis[i2] = 1;}printf( "%lld\n", ans );return 0; }

CF1251E2 Voting (Hard Version)

CF1251E2

如果將$m$的限制變成時間限制，第$i$個人的投票必須在$n?m_i?1$的時間以前（包括這個時刻）

注意：是以0時刻開始算起的

投票，否則就會產生$p_i$的罰款

這就巧妙地轉化成了貪心經典——不守交規

按照截止時間排序，每個人投票需要一個時間

• 如果時間還有剩，這個人就可以不被罰
• 如果沒有剩，那么往前面找最小的罰金（必須比現在的罰金小）
  • 有就選擇交換這兩個人的投票時間，將這個人入反悔堆，罰金是不可避免的，只不過變成了交最小的罰金
  • 沒有就老老實實讓這個人交罰金

#include <queue> #include <cstdio> #include <algorithm> using namespace std; #define int long long #define maxn 200005 struct node { int p, m; }vote[maxn]; priority_queue < int, vector < int >, greater < int > > q; int T, n;signed main() {scanf( "%lld", &T );while( T -- ) {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%lld %lld", &vote[i].m, &vote[i].p );vote[i].m = n - vote[i].m - 1;}sort( vote + 1, vote + n + 1, []( node x, node y ) { return x.m < y.m; } );while( ! q.empty() ) q.pop();int ans = 0;for( int i = 1;i <= n;i ++ )if( q.size() <= vote[i].m ) q.push( vote[i].p );elseif( ! q.empty() and q.top() < vote[i].p )ans += q.top(), q.pop(), q.push( vote[i].p );elseans += vote[i].p;printf( "%lld\n", ans );}return 0; }

CF436E Cardboard Box

CF436E

• 貪心操作1：選擇激活某個關卡的第一顆星 花費為最小的$ai$
• 貪心操作2：選擇激活某個關卡的第二顆星 花費為最小的$bj?aj$
• 反悔操作1：反悔最大花費的只激活了第一顆星的關卡 直接將花費最小的未激活關卡激活完2顆星 花費為$bi?aj$
• 反悔操作2：反悔最大花費的2顆星全激活的關卡 直接將花費最小的未激活關卡2顆星激活完 花費為$bi?(bj?aj)$

直接開五個堆維護，代碼里有詳細注釋

#include <queue> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define Pair pair < int, int > #define int long long #define maxn 300005 #define inf 1e18 priority_queue < Pair, vector < Pair >, greater < Pair > > q1, q2, q3; priority_queue < Pair > q4, q5; int n, m; int ans[maxn], a[maxn], b[maxn];/* q1: 關卡激活為0顆星的a貪心策略1：選擇花費最小的還是0顆星的關卡激活成1顆星小根堆 q2: 關卡激活為1顆星的b-a貪心策略2：選擇花費最小的激活1顆星的關卡激活成2顆星小根堆 q3: 關卡激活為0顆星的b反悔策略12：回收一顆星后直接激活最小花費某個關卡的兩顆星小根堆 q4: 關卡激活為1顆星的a反悔策略1：反悔最大花費的激活1顆星的關卡操作變成激活為0大根堆 q5: 關卡激活為2顆星的b-a返回策略2：反悔最大花費的激活2顆星的關卡操作變成只激活1大根堆 */void add0( int x ) {ans[x] = 0;q1.push( make_pair( a[x], x ) );q3.push( make_pair( b[x], x ) ); }void add1( int x ) {ans[x] = 1;q2.push( make_pair( b[x] - a[x], x ));q4.push( make_pair( a[x], x ) ); }void add2( int x ) {ans[x] = 2;q5.push( make_pair( b[x] - a[x], x ) ); }signed main() {scanf( "%lld %lld", &n, &m );q1.push( make_pair( inf, n + 1 ) );q2.push( make_pair( inf, n + 1 ) );q3.push( make_pair( inf, n + 1 ) );q4.push( make_pair( -inf, n + 1 ) );q5.push( make_pair( -inf, n + 1 ) ); for( int i = 1;i <= n;i ++ ) {scanf( "%lld %lld", &a[i], &b[i] );add0( i );}int ret = 0;for( int i = 1;i <= m;i ++ ) {int i1 = q1.top().second;int i2 = q2.top().second;int i3 = q3.top().second;int i4 = q4.top().second;int i5 = q5.top().second;while( q1.size() > 1 and ans[i1] ^ 0 ) q1.pop(), i1 = q1.top().second;while( q2.size() > 1 and ans[i2] ^ 1 ) q2.pop(), i2 = q2.top().second;while( q3.size() > 1 and ans[i3] ^ 0 ) q3.pop(), i3 = q3.top().second;while( q4.size() > 1 and ans[i4] ^ 1 ) q4.pop(), i4 = q4.top().second;while( q5.size() > 1 and ans[i5] ^ 2 ) q5.pop(), i5 = q5.top().second;int w1 = q1.top().first;int w2 = q2.top().first;int w3 = q3.top().first;int w4 = q4.top().first;int w5 = q5.top().first;//i:表示未激活的關卡 j:表示已激活的關卡 int t1 = w1; //貪心操作1：選擇激活某個關卡的第一顆星 花費為最小的aiint t2 = w2; //貪心操作2：選擇激活某個關卡的第二顆星 花費為最小的bj-ajint t3 = w3 - w4; //反悔操作1：反悔最大花費的只激活了第一顆星的關卡 直接將花費最小的未激活關卡激活完2顆星 花費為bi-aj int t4 = w3 - w5; //反悔操作2：反悔最大花費的2顆星全激活的關卡 直接將花費最小的未激活關卡2顆星激活完 花費為bi-(bj-aj) int Min = min( min( t1, t2 ), min( t3, t4 ) );ret += Min;if( Min == t1 ) q1.pop(), add1( i1 );else if( Min == t2 ) q2.pop(), add2( i2 );else if( Min == t3 ) q3.pop(), q4.pop(), add2( i3 ), add0( i4 );else q3.pop(), q5.pop(), add2( i3 ), add1( i5 );}printf( "%lld\n", ret );for( int i = 1;i <= n;i ++ ) printf( "%lld", ans[i] );return 0; }

總結

以上是生活随笔為你收集整理的专题突破之反悔贪心——建筑抢修，Cow Coupons G， Voting (Hard Version)，Cardboard Box的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。