首页 > 代码库 > 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了好多次的题目