南宁网站建设哪家好,牡丹江网站seo,大型平面设计网站,社交网站盈利吗题意
给出一堆线段。 询问者每次可以询问一个整数点#xff0c;回答者告诉询问者这个点被多少根线段包括。 问询问者最多问多少次#xff0c;还不能确定任意一个整数点都不可能被所有的线段包含。 题解
首先用O(n)的方法计算出来每个点被多少条线段包含。 突破点#x…题意
给出一堆线段。 询问者每次可以询问一个整数点回答者告诉询问者这个点被多少根线段包括。 问询问者最多问多少次还不能确定任意一个整数点都不可能被所有的线段包含。 题解
首先用O(n)的方法计算出来每个点被多少条线段包含。 突破点 我们考虑什么情况下不能确定存在整数点被所有线段包括。 反向思考当存在一个点被所有的线段包括了那么必定有 cnt(x1)cnt(x2)...cnt(xi)cnt(xi1)...cnt(xm)cnt(x1)cnt(x2)...cnt(xi)cnt(xi1)...cnt(xm)cnt(x_1)=cnt(x_{i+1})>=...>=cnt(x_m) 也就是目前询问的点形成了一个凸函数。 一旦我们询问的点不能形成一个凸函数的话我们就可以断定不存在一个点使得这个点被所有的线段包含。 因此我们只需要找出最长的凸函数就可以了。 这个可以分成两段最长非减序列以及最长非增序列枚举一个点然后拼接两段的选一个最长的长度就是答案。 代码
#include iostream
#include cstdio
#include algorithm
#include cstring
using namespace std;
int n,m,l,r;
const int maxn 100007;
int a[maxn],addmark[maxn],dp[maxn],lis[2][maxn],slis[maxn];
int cnt 0;
int main(){cinnm;for(int i 0;i n;i){scanf(%d%d,l,r);addmark[l] ;addmark[r1] --;}int sum 0;for(int i 1;i m;i){sum addmark[i];a[i] sum;}memset(dp,0x3f,sizeof(dp));for(int i 1;i m;i){int pos upper_bound(dp,dpm,a[i])-dp;dp[pos] a[i];lis[0][i] pos1;}memset(dp,0x3f,sizeof(dp));for(int i m;i 1;i--){int pos upper_bound(dp,dpm,a[i])-dp;dp[pos] a[i];lis[1][i] pos1;slis[i] max(slis[i1],lis[1][i]);}int ans 0;for(int i 1;i m;i){//printf(i:%d %d %d\n,i,lis[0][i],lis[1][i]);ans max(ans,lis[0][i] slis[i1]);}coutansendl;return 0;
}
