hdu 6180 Schedule

时间：2017-08-24 22:09:42 收藏：0 阅读：301

Schedule

Problem Description

There are N schedules, the i-th schedule has start time

Input

The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers

Output

For each test case, print the minimum possible number of machines and the minimum sum of all working times.

最近真的是愈发感觉自己很菜了很伤感啊....

好不容易感觉有道签到题目可以写结果写了两个小时

WA了6发 T了2发菜的一匹~~~

题意：工厂加工零件问最少能用几个机器和机器所用的最少的时间

大概是不知道套路吧...等明天看别人的帖子再学学新的套路

就是贪心但是我只想到了选择间距最短的用一个机器这样能保证所用的时间最少

但，但是我就是不会写就很GG

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int st;//记录入点和出点
    int flag;//如果是入点就+1，否则就-1
}s[100000*2+100];

int L[100000+100],R[100000+100];//记录机器的开始时间 和 结束时间

bool cmp(node a,node b)
{
    if(a.st != b.st)
        return a.st<b.st;//就是按照端点排序
    else
        return a.flag < b.flag;//因为区间结束的时候 和另一个区间开始的会重叠
        //so 让区间先结束 然后在开始 这样子的吧
}

void init()
{
    memset(L,0,sizeof(L));
    memset(R,0,sizeof(R));
}
int main ()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        init();
        int n;
        scanf("%d",&n);
        int m=0;
        for(int i=0;i<n;i++)
        {
            int st,e;
            scanf("%d %d",&st,&e);
            s[m].st = st,s[m++].flag=1;//左端点+1
            s[m].st = e,s[m++].flag=-1;//右端点-1
        }
        sort(s,s+m,cmp);
        int sum=0,ans=0;
        for(int i=0;i<m;i++)
        {
            sum+=s[i].flag;
            if(sum>ans)
            {
                ans = sum;
                L[sum] = s[i].st;
            }
        }
        sum=0,ans=0;
        for(int i=m-1;i>=0;i--)
        {
            sum-=s[i].flag;
            if(sum>ans)
            {
                ans = sum;
                R[sum] = s[i].st;
            }
        }
        ll res=0;
        for(int i=1;i<=ans;i++)
        {
            res += (R[i]-L[i]);
        }//因为最后就是R-L  所以这里不用管 R[i]和L[i]是否对应
        cout<<ans<<" "<<res<<endl;
    }
}

原文：http://www.cnblogs.com/Draymonder/p/7425415.html