HDU - 1050

佚名 7年前 (2019-04-17) 随笔 1002人围观抢沙发百度已收录

wa了5遍？！！

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：遍历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;
}