→題目鏈接←

最開始看到是USACO就想n^2搞，但是看到100000就虛了...

先以左端點從小到大為第一關鍵字排序

這樣就會保證，當我們從掃到 i 時，如果MaxRight大于等于 i 的right，那么 i 一定是不可行的

所以如果碰到這樣的狀況，就令ans=min(ans,i) ?*下標從0開始

復雜度nlogn

這...應該算貪心吧...

代碼：

#include<iostream> #include<cstdio> #include<algorithm>using namespace std;struct node{int l,r,num;friend bool operator < (node a,node b){return a.l<b.l;} };int n; node a[100010];int main(){scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d%d",&a[i].l,&a[i].r);a[i].num=i;}sort(a,a+n);int Max=0,ans=n;for(int i=0; i<n; i++){if(a[i].r<=Max)ans=min(ans,a[i].num);Max=max(Max,a[i].r);}printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的bzoj 3375: [Usaco2004 Mar]Paranoid Cows 发疯的奶牛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。