POJ - 3017 https://vjudge.net/problem/13735/origin
题意:
给定一大堆线段, 问用这些线段覆盖一个连续区间 1-x 的最小使用线段的数量.
题解
考虑一个这样的贪心:
先按照左端点排序, 若左端点一样则谁长谁在前. 现在判无解就方便了, 记录一下前缀 max 即可. 然后现在要最小化选择.
记录一个最右端点 \(R\), 一个暴力的办法是暴力循环判断所有线段是否满足条件, 这样显然超时, 你决定优化一下常数, 所以你记录一下从哪个线段开始才 \(l_i \ge R\). 你以为你是常数优化, 其实你复杂度就对了 (\(O(n)\))...
- const int QAQ=2020;
- while(QAQ){
- register int l=r+1;
- for(register int t=can;t<=n;++t){
- if(data[t].l<=l&&data[t].r>=l)
- r=max(r,data[t].r);
- if(data[t].l>r) {can=t;break;}
- }
- if(l>r)break;
- else if(++ans,r>=T) break;
- }
分析一下这个复杂度, 首先是 can 一定会一直变大, 并且变大 \(O(n)\) 的代价是 \(O(n)\) 的, 所以就是 \(O(n)\) 的. 你可能会说跳出那个 for 循环不一定是由于 break, 但是如果不是那个 break 跳掉的话说明不存在更多合法方案了.
- //@winlere
- #include
- #include
- #include
- #include
- #include
- using namespace std; typedef long long ll;
- inline int qr(){
- register int ret=0,f=0;
- register char c=getchar();
- while(c<48||c>57)f|=c==45,c=getchar();
- while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
- return f?-ret:ret;
- }
- int n,T,ans,top,r;
- struct LINE{
- int l,r;
- LINE(){l=r=0;}
- LINE(const int&a,const int&b){l=a;r=b;}
- }data[25005];
- inline bool cmp(const LINE&a,const LINE&b){
- if(a.l!=b.l) return a.l<b.l;
- return a.r>b.r;
- }
- queue q;
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in.in","r",stdin);
- //freopen("out.out","w",stdout);
- #endif
- int n=qr();T=qr();
- for(register int t=1,t1,t2;t<=n;++t){
- t1=qr();t2=qr();
- data[t]=LINE(t1,t2);
- }
- sort(data+1,data+n+1,cmp);
- while(r<T){
- register int ew=r+1;
- for(register int t=1;t<=n;++t)
- if(data[t].l<=ew&&data[t].r>=ew)
- r=max(r,data[t].r);
- else if(data[t].l>r){
- top=t;
- break;
- }
- if(ew>r)break;
- else ++ans;
- }
- if(r<T) ans=-1;
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3085931.html