首页 > 代码库 > CODEVS 1214
CODEVS 1214
1214 线段覆盖
题意:中文题
思路:贪心,先按l排序后按r排序,每次标记当前剩下线段的最右端,因为l是从小到达有序的,所以不需要考虑左端点,只需要考虑右边尽量往左端点取就是了
AC代码:
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; struct Node{ int l, r; bool friend operator< ( Node a, Node b){ if(a.l==b.l) return a.r<b.r; return a.l<b.l; } }; Node arr[105]; int n,ans=-1; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int i=1; i<=n; ++i){ int x,y; cin>>x>>y; arr[i].l=min(x,y); arr[i].r=max(x,y); } sort(arr+1,arr+1+n); int p=inf; for(int i=1; i<=n; ++i){ if(arr[i].r>=p){ if(arr[i].l<p){ ans++; } else p=arr[i].r; } else{ ans++; p=arr[i].r; } } cout<<n-ans<<"\n"; return 0; }
CODEVS 1214
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。