Problem

https://www.luogu.org/problemnew/show/P2519

Solution

正难则反，转换模型。

考虑有一些人一定说谎，则选出不一定说谎的最多的说真话的人。

转化为带权区间覆盖问题。

即可以得出分数排序之后每人代表的区间。
即对于一个区间，里面只要说的话全部相同即为真话。
如果说的话不同，则区间一定不同。
如果两个不同的区间相交，则交集的人说的话一定矛盾。

找出最多的不相交的区间，里面已经装有了一些人，这就是我们找到的说真话的人。
剩下的人任意排布即可。

Code

// Code by ajcxsu
// Problem: a

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
#define INF (0x3f3f3f3f)
const int N=1e5+10;
int C[N];
void updata(int x, int d) { while(x<N) C[x]=max(C[x], d), x+=lowbit(x); }
int query(int x) { int ret=0; while(x) ret=max(ret, C[x]), x-=lowbit(x); return ret; }

int h[N], to[N], W[N], nexp[N], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

map<pair<int, int>, int> mp;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    int l, r, len;
    for(int i=0;i<n;i++) {
        cin>>l>>r, len=n-l-r;
        if(len>0) mp[make_pair(l+1, n-r)]++;
    }
    for(auto x:mp)
        ins(x.first.second, x.first.first-1, min(x.second, x.first.second-x.first.first+1));
    int nf=0, ans;
    for(int i=1;i<=n;i++) {
        for(int u=h[i];u;u=nexp[u])
            nf=max(nf, query(to[u])+W[u]);
        updata(i, nf);
    }
    printf("%d\n", n-nf);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2519.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆