首先考虑分割线能分割一条线当且仅当分割线一个端点在这条线的ab中间,另一端点在外面,也就是分割线对应的一条弧不能同时有这条线的两个端点
每条线的两端点都染同色,然后分段,一段里面颜色互不相同,分割线就是一段的开始连到结尾,割掉这段里的颜色的线,求最小的段数ans,答案就是(ans+1)/2 暴力是要枚举起点,考虑优化,一个起点不是最优一定是从最优分割的一个块的中间开始分割的,也就是第一段向前延伸还能加进新点,现在考虑最短的线的a+1这个点作为起点,那么这块一定能延伸到最短的线的b,因为这是最短的,不可能有另一条线的两个端点在同时(a+1,b)了,然后能到b,就不能向前延伸了,前面一个就是和b同色的a了 所以选定这个起点贪心分段即可 我的证明应该没错吧……?反正是A了#include#include using namespace std;const int N=1000005;int n,st,mn=1e9,c[N],v[N],ti,ans;int read(){ int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p>='0'&&p<='9') { r=r*10+p-48; p=getchar(); } return r*f;}int main(){ n=read(); for(int i=1;i<=n;i++) { int a=read(),b=read(); if(a>b) swap(a,b); c[a]=c[b]=c[a+n*2]=c[b+n*2]=i; if(b-a