[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=2298
[算法]
考虑用总人数 - 最多人说真话
显然 ， 对于每个人 ， 如果他说的是真话 ， 那么他的排名必然在[ai + 1 , n - bi]中 ， 否则不合法
统计出每个合法区间相同的个数
那么问题转化为了 :
现在有一些线段 ， 每条线段[li , ri]有一个权值wi , 从中选取若干条使得权值和最大
考虑dp
将区间按右端点排序 ， 用fi表示前i个区间的最大权值和 ， 通过二分求出最大的pos使得rpos < li
有转移方程fi = max{fi-1 , fpos + w}
答案即为n - fn
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; struct segment
{
int l , r;
} s[N];
struct info
{
int l , r;
int value;
} e[N]; int n , m , tot;
int a[N] , b[N] , dp[N]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline bool cmpa(segment a , segment b)
{
if (a.l != b.l) return a.l < b.l;
else return a.r < b.r;
}
inline bool cmpb(info a , info b)
{
return a.r < b.r;
} int main()
{ read(n);
for (int i = ; i <= n; ++i)
{
read(a[i]);
read(b[i]);
if (a[i] + <= n - b[i])
s[++tot] = (segment){a[i] + , n - b[i]};
}
sort(s + , s + tot + , cmpa);
for (int i = ; i <= tot; ++i)
{
if (s[i].l == s[i - ].l && s[i].r == s[i - ].r)
{
if (e[m].value != s[i].r - s[i].l + )
++e[m].value;
continue;
} else
e[++m] = (info){s[i].l , s[i].r , };
}
sort(e + , e + m + , cmpb);
for (int i = ; i <= m; ++i)
{
int l = , r = i , k = ;
while (l <= r)
{
int mid = (l + r) >> ;
if (e[mid].r < e[i].l)
{
k = mid;
l = mid + ;
} else r = mid - ;
}
dp[i] = max(dp[i - ] , dp[k] + e[i].value);
}
printf("%d\n" , n - dp[m]); return ; }