HDU - 1050

wa了5遍？！！

（1）前4遍，思路没简化，企图模拟整个过程，但是调用sort函数时由于没有把奇数的屋子和偶数的屋子统一，排序出了问题。

思路：遍历n段，每次只扫未被标记过的一段，ans++并且从该段出发，访问到第n段，将所有和该段不重叠的段标记为1，ans不变。

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 500

#define rep(i,a,b) for(int i=(a);i<(b);i++)

#define ll long long

struct gg{

    int s,e;

}a[maxn];

int vis[maxn];

int cmp(gg k1,gg k2){

    return k1.s<k2.s;

}

int main()

{

    int T;

    cin>>T;

    while(T--){

        int n;

        memset(vis,0,sizeof(vis));

        scanf("%d",&n);

        rep(i,0,n){

            int x,y;

            scanf("%d%d",&a[i].s,&a[i].e);

            if(a[i].s>a[i].e)

                swap(a[i].s,a[i].e);

            a[i].s=a[i].s%2==0?a[i].s:a[i].s+1;

            a[i].e=a[i].e%2==0?a[i].e:a[i].e+1;

        }

        sort(a,a+n,cmp);

        int ans=0;

        rep(i,0,n){

            if(!vis[i]){

                int last=a[i].e;

                ans++,vis[i]=1;

                rep(j,i+1,n){

                    if(!vis[j]){

                        if(a[j].s>last){

                            last=a[j].e;

                            vis[j]=1;

                        }

                    }

                }

            }

        }

        ans*=10;

        printf("%d\n",ans);

    }

    return 0;

}

　　（2）简化思路：把从一个屋子到另一个屋子看作线段，计算所有线段中被重叠次数最多的线段对应的重叠次数。理解：和某线段不重叠的线段不计入总时间。只要知道重叠次数最多的线段，就能知道有多少线段要计入总时间。

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 500

#define rep(i,a,b) for(int i=(a);i<(b);i++)

#define ll long long

int vis[maxn];

int main()

{

    int T;

    cin>>T;

    while(T--){

        int n;

        memset(vis,0,sizeof(vis));

        scanf("%d",&n);

        rep(i,0,n){

            int x,y;

            scanf("%d%d",&x,&y);

            if(x>y)

                swap(x,y);

            if(x%2)

                x++;

            if(y%2)

                y++;

            for(int j=x;j<=y;j+=2)

                vis[j]++;

        }

        int ans=0;

        rep(i,0,401){

            ans=max(ans,vis[i]);

        }

        ans*=10;

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

HDU - 1050

最新文章

热门文章