标签：__ ... int long Greedy file define

贪心整合包

Tricks

有些时候贪心是无法证明交换性的，一定要注意交换性是不是对的！即“我不要的你是否一定能拿到”
反悔贪心的用法：一个物品必然被某个人选，那么我们可以把它加进优先队列里，以后来人的时候再慢慢替换。
和区间有关的匹配可以用 Hall 定理很好地解释！
Hall 定理求最大匹配是 \(|X|-\max(|S|-R(|S|))\)，想求 \(\max(|S|-R(|S|))\)，可以考虑求 \(R(|S|)\) 的补集的最大值，这样 \(\max\) 里面是加号，有利于处理。

ARC076D Exhausted?

简要题意：有 \(n\) 个人 \(m\) 张椅子，第 \(i\) 个人只愿意坐在第 \(L_i\) 个椅子之前或第 \(R_i\) 个椅子之后，求至多有几个人坐下来。\(n,m\le 2\times 10^5,0\le L_i<R_i\le m+1\)。

Fake Solution

直接贪心，把所有人按 \(L_i\) 从小到大排序，\(L_i\) 相同的按 \(R_i\) 从大到小排序，然后贪心选，如果能放左边就放左边，否则放到右边的一个队列里面，左边放完之后再对右边排序处理。

Hack

bigger:

Real Solution

为什么这种贪心是错的？因为我们想“证明”的交换性是错的。一开始想的“交换性”是基于“如果我的左端点靠前，那‘别人占我的位置，我拿其他位置’不如‘我占我的位置，别人拿那个其他位置’”，但是这是错的，因为“其他位置”别人不一定拿得到。没有正视这个漏洞而随手写了一发，居然过了，但是被题解区 hack 了。

做法一

还是要处理这种情况，可以考虑的一点是反悔贪心。事实上，我们之前的结论中有一点是正确的：我的这个位置，要么我占了，要么回头别人占了，一定不会空着。所以用反悔贪心来考虑，如果我有位置，我就暂时占着；如果我没位置了，那我就到前面去看看有没有适合抢的，如果有就抢一个，把多出来的那个塞到后面去。什么情况下“适合抢”呢？如果我的 \(R_i\) 要大于对方的 \(R_j\)，那我确实更紧迫，留下我不如留下他，这个交换性是可以证的，所以我就可以把他换出来。剩下的右半部分照样处理。

做法二

这种问题可以被视为是最大匹配问题，可以尝试用 Hall 定理解决。Hall 定理有一个很有用的推论：最大匹配的大小为 \(|X|-\max(|S|-R(|S|))\)。对应到这道题上，我们要求最大匹配，就是要找出若干个集合，使（集合数量 - 它们的并的大小）最大，答案为 \(n\) 减去这个最大值。对于最大值中出现减号的问题，可以考虑将其取补集。所以变成最大化（集合数量 + 区间的交的大小），则发现区间的交可以偏小，所以枚举这个交集看有几个区间包含它即可。可以线段树优化到 \(O(n\log n)\)。

Fake Code

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rev(i,a,b) for(int i=(a);i>=(b);i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define fi first
#define se second
using namespace std; typedef long long ll; using pii = pair<int,int>;
constexpr int N=2e5+5;
int n,m; vector<int> lis[N]; priority_queue<int> q;
signed main(){
    // Fin("hh.in");
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n>>m; For(i,1,n) { int x,y; cin>>x>>y; lis[x].push_back(y); }
    int ans=0,use=0; vector<int> vec; for(int u:lis[0]) vec.push_back(m-u+1);
    For(x,1,m){
        for(int u:lis[x]) q.push(u);
        while(q.size()&&use<x) use++,q.pop();
        while(q.size()) vec.push_back(m-q.top()+1),q.pop();
    }
    sort(vec.begin(),vec.end()); //debug(vec,use);
    int lim=m-use; use=0; for(int x:vec) if(use<min(x,lim)) use++; else ans++;
    cout<<ans<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: November 08 Wed, 07 : 51 : 25

Real Code（做法一）

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rev(i,a,b) for(int i=(a);i>=(b);i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=2e5+5; using pii = pair<int,int>;
int n,m; pii a[N]; priority_queue<int,vector<int>,greater<>> q;
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n>>m; For(i,1,n) cin>>a[i].fi>>a[i].se;
    sort(a+1,a+1+n); int use=0; vector<int> vec;
    For(i,1,n){
        q.push(a[i].se);
        if(use<a[i].fi) use++;
        else vec.push_back(m-q.top()+1),q.pop();
    }
    int lim=m-use; use=0; int ans=0; sort(vec.begin(),vec.end()); debug(vec);
    for(int x:vec) if(use<min(x,lim)) use++; else ans++;
    cout<<ans<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: November 08 Wed, 09 : 01 : 49

暴力&gen（对拍用）

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rev(i,a,b) for(int i=(a);i>=(b);i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
using namespace std; typedef long long ll;
constexpr int N=15;
int n,m,L[N],R[N],ans,vis[N];
void dfs(int u,int res){
    if(res>ans) return;
    if(u==n+1) return ans=min(ans,res),void();
    For(i,1,L[u]) if(!vis[i]){
        vis[i]=1; dfs(u+1,res); vis[i]=0;
    }
    For(i,R[u],m) if(!vis[i]){
        vis[i]=1; dfs(u+1,res); vis[i]=0;
    }
    dfs(u+1,res+1);
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n>>m; For(i,1,n) cin>>L[i]>>R[i];
    ans=1e9; dfs(1,0); cout<<ans<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: November 08 Wed, 08 : 22 : 39

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rev(i,a,b) for(int i=(a);i>=(b);i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
using namespace std; typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long rnd(ll l,ll r) { return uniform_int_distribution<ll>(l,r)(rng); }
void rnd(long long& l,long long& r,long long n) { l=rnd(1,n); r=rnd(1,n); if(l>r) swap(l,r); }
void rnd(int& l,int& r,int n) { l=rnd(1,n); r=rnd(1,n); if(l>r) swap(l,r); }
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    int n=12,m=10; cout<<n<<' '<<m<<'\n';
    For(i,1,n) { int l=0,r=0; while(l==r) l=rnd(0,m+1),r=rnd(0,m+1);; if(l>r) swap(l,r);; cout<<l<<' '<<r<<'\n'; }
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: November 08 Wed, 08 : 24 : 38

标签：__,...,int,long,Greedy,file,define
From： https://www.cnblogs.com/Charlie-Vinnie/p/17816690.html

Greedy

贪心整合包

ARC076D Exhausted?

做法一

做法二

相关文章

赞助商

阅读排行