首页 > 代码库 > wa了好多次的题目
wa了好多次的题目
细节总是理解错
用贪心做的,据说扫描线+线段树,也可以,改天试试
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 7 struct node{ 8 int l,r; 9 int index; 10 }a[50005],b[4]; 11 int ans[50005]; 12 bool cmp(node a,node b) 13 { 14 return a.l<b.l; 15 } 16 bool cmp2(node a,node b) 17 { 18 return a.r>b.r; 19 } 20 int main() 21 { 22 int t; 23 scanf("%d",&t); 24 while(t--) 25 { 26 int n; 27 scanf("%d",&n); 28 for(int i=1;i<=n;i++) 29 { 30 scanf("%d%d",&a[i].l,&a[i].r); 31 a[i].index=i; 32 } 33 sort(a+1,a+n+1,cmp); 34 int cnt=0; 35 b[1]=a[1],b[2]=a[2]; 36 for(int i=3;i<=n;i++) 37 { 38 b[3]=a[i]; 39 sort(b+1,b+4,cmp); 40 if(b[3].l<=b[2].r && b[3].l<=b[1].r) 41 { 42 sort(b+1,b+4,cmp2); 43 ans[cnt++]=b[1].index; 44 swap(b[1],b[3]); 45 } 46 else sort(b+1,b+4,cmp2); 47 } 48 sort(ans,ans+cnt); 49 printf("%d\n",cnt); 50 for(int i=0;i<cnt;i++) 51 printf("%d%c", ans[i], i == cnt-1 ? ‘\n‘ : ‘ ‘); 52 } 53 return 0; 54 }
wa了好多次的题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。