牛客54057 谁在说谎（思维+dp）

牛客54057 谁在说谎（思维+dp）

题意：

有n个学生，每个学生都有一个成绩，但是现在成绩是未知的。
第i个学生说有a(i)个人成绩比他高，b(i)个人成绩比他低。
问最少有多少个学生说谎。

数据范围：n<=1e5，0<=a(i),b(i)<=n，可能有相同的分数。

解法：

考虑将问题变为计算最多有多少个人没有说谎.
对于每个学生(a,b),可以确定出一个区间[a+1,n-b],
这个区间内的所有学生分数是相同的.
将相同区间合并为三元组(l,r,cnt),
则每个三元组对应一个区间,这个区间有权值cnt.
问题变为计算有多少区间不相交,且权值和最大.
对三元组按右端点排序,然后dp一下即可:
dp[i]=max{dp[j]}+ee[i]t,其中ee[j].r<ee[i].l.
用指针维护左边满足ee[j].r<ee[i].l的max{dp[j]},这样就可以O(1)转移了.

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+5;
struct Node{int l,r;bool operator==(const Node& a)const{return l==a.l&&r==a.r;}
}e[maxm];
struct EE{int l,r;int cnt;
}ee[maxm];
int d[maxm];
int n;
bool cmp(Node a,Node b){//按左端点从小到大排序.if(a.l!=b.l)return a.l<b.l;return a.r<b.r;
}
bool cmp2(EE a,EE b){if(a.r!=b.r)return a.r<b.r;return a.l<b.l;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;int tot=n;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;int l=a+1,r=n-b;e[i]={l,r};}sort(e+1,e+1+n,cmp);int m=0;for(int i=1;i<=n;i++){if(e[i].l>e[i].r)continue;int j=i;while(j<=n&&e[j]==e[i]){j++;}j--;ee[++m]={e[i].l,e[i].r,j-i+1};ee[m]t=min(ee[m]t,ee[m].r-ee[m].l+1);//注意,这里需要取mini=j;}n=m;sort(ee+1,ee+1+n,cmp2);int ans=0;int last=0;int ma=0;for(int i=1;i<=n;i++){d[i]=ee[i]t;while(last+1<i&&ee[last+1].r<ee[i].l){last++;ma=max(ma,d[last]);}if(last&&ee[last].r<ee[i].l){d[i]+=ma;}ans=max(ans,d[i]);}cout<<tot-ans<<endl;return 0;
}