洱源名师工作室网站建设,招代理,济南建设局网站公式,浙江小九天建设集团网站思路#xff1a;可以贪心#xff0c;也可以最短路。 贪心写法#xff1a;因为在保证合法的前提下#xff0c;我们选择的区间一定要右端点尽量靠后才行#xff0c;于是我们每次就选择一个合法的并且右端点最靠后的区间就好了#xff08;如果没有合法的输出-1即可#xff…思路可以贪心也可以最短路。 贪心写法因为在保证合法的前提下我们选择的区间一定要右端点尽量靠后才行于是我们每次就选择一个合法的并且右端点最靠后的区间就好了如果没有合法的输出-1即可。时间复杂度O(nlogn)排序是nlogn的贪心是O(n)的。 #includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
#define maxn 25005int n,t,ans;
int last[1000005];struct node{int l,r;bool operator (const node a)const{return la.l||(la.lra.r);}
}a[maxn];inline int read(){int x0;char chgetchar();for (;ch0||ch9;chgetchar());for (;ch0ch9;chgetchar()) xx*10ch-0;return x;
}int main(){nread(),tread();for (int i1;in;i) a[i].lread(),a[i].rread();sort(a1,an1);int cnt0;for (int i1;in;i)if (a[i].l!a[i1].l) a[cnt]a[i];ncnt;int now0;for (int i1;in;i){int x0;bool flag0;while (a[i].lnow1in) xmax(x,a[i].r),i,flag1;if (!flag){ans-1;break;}if (xnow) nowx,ans;i--;}if (now!t) ans-1;printf(%d\n,ans);return 0;
}最短路写法区间[l,r]表示可以从l-1走到r那么我们就把l-1连一条权值为1的边到r即可然后又因为区间可以有交集所以还需要将i向i-1连一条权值为0的边然后以0为起点跑最短路即可以0为起点是因为是l-1连向r。时间复杂度O(TlogT) #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includequeue
#includecmath
using namespace std;
#define maxn 1000005
#define inf 1e9int n,t,tot;
int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2],dis[maxn];
bool vis[maxn];inline int read(){int x0;char chgetchar();for (;ch0||ch9;chgetchar());for (;ch0ch9;chgetchar()) xx*10ch-0;return x;
}void add(int a,int b,int c){son[tot]b;pre[tot]now[a];now[a]tot;val[tot]c;
}void link(int a,int b,int c){add(a,b,c);
}struct node{int id,val;node(){}node(int a,int b){ida,valb;}bool operator (const node a)const{return vala.val;}
};
priority_queuenode heap;void dijkstra(int x){memset(dis,127,sizeof(dis)),dis[x]0;heap.push(node(x,0));while (!heap.empty()){node xheap.top();heap.pop();int idx.id,vx.val;if (vis[id]) continue;vis[id]1;for (int pnow[id];p;ppre[p])if (dis[son[p]]vval[p]) heap.push(node(son[p],dis[son[p]]vval[p]));}
}int main(){nread(),tread();for (int i1,a,b;in;i) aread(),bread(),link(a-1,b,1);for (int i1;it;i) link(i,i-1,0);dijkstra(0);if (dis[t]1e9) puts(-1);else printf(%d\n,dis[t]);return 0;
} 转载于:https://www.cnblogs.com/DUXT/p/6044799.html
