HDOJ6180 Schedule 前缀和+瞎搞+输入挂

题目

给出个加工任务的开始时间和结束时间，问最少要用多少台机器可以完成这些任务，同一台机器上的任务时间不能有重叠，但允许守尾相接。对于每组用例，输出两个整数，分别表示最少用的机器台数和所有机器用的总时间。一台机器的用时为它最后的结束时间减它最开始启动的时间，中间不会停机。

$ T (1 <= T <= 100) , N (0 < N <= 100000,0<=s_i<e_i<=1e9)$

Sample Input

1
3
1 3//记住是左闭右开
4 6
2 5

Sample Output

2 8

分析

这个题第一问是很简单,就是最大重叠数,用前缀和就可以解决了.对于第二个问,我们只需要考虑在哪些地方一定需要增加一台机器,把这个时间记录下来,一共记为$\sum first_i$,同理从后往前,可以算出$\sum last_i$,两个相减就可以了.

然后这个题的$s_i,t_i$都很大,所有我们需要离散化一下,采用 sort+unique+unordered_map的方法

最后但也是最重要的,数据规模很大,需要采用读入挂,T到怀疑人生,以后注意,如果超过1e6个数就采用读入挂

代码

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int MAXN=5e5+7;
const int BUF_SIZE=409600;
int sum[MAXN];
unordered_map<int,int>mp;
int l[MAXN],r[MAXN],a[MAXN];
int fp[MAXN];
struct {
    int cur, eof;
    char buf[BUF_SIZE];
    char next_char() {
        if (cur == BUF_SIZE) {
            if (eof) return -1;
            int bytes = fread(buf, 1, BUF_SIZE, stdin);
            if (bytes < BUF_SIZE) {
                memset(buf + bytes, -1, BUF_SIZE - bytes);
                buf[bytes] = -1;
                eof = 1;
            }
            cur = 0;
        }
        return buf[cur++];
    }
    int next_int() {
        int x = 0;
        char ch = next_char();
        while (ch < '0' || ch > '9') {
            if (ch == -1) return 0;
            ch = next_char();
        }
        while (ch >= '0' && ch <= '9') {
            x = x*10 + ch - '0';
            ch = next_char();
        }
        return x;
    }
} IO = {BUF_SIZE,};
int main(){
	int T=IO.next_int();
	while(T--){
		mp.clear();
		memset(sum,0,sizeof(sum));
		memset(fp,0,sizeof(fp));
		int N=IO.next_int();
		for(int i=0;i<N;++i){
			l[i]=IO.next_int();
			r[i]=IO.next_int();
			--r[i];
			a[i]=l[i];a[N+i]=r[i];
		}

		sort(a,a+2*N);//离散化
		int cnt=unique(a,a+2*N)-a;
		int tot=1;
		for(int i=0;i<cnt;++i){
			mp[a[i]]=tot;
			fp[tot]=a[i];
			++tot;
		}

		for(int i=0;i<N;++i){
			int x=l[i],y=r[i];
			++sum[mp[l[i]]];--sum[mp[r[i]]+1];
		}

		int ans=0;
		long long first=0,last=0;
		for(int i=1;i<=tot;++i){
			sum[i]+=sum[i-1];
			if(sum[i]>ans){
				first+=fp[i]*(sum[i]-ans);
				ans=sum[i];
			}
		}
		printf("%d ",ans);
		ans=0;
		for(int i=tot;i>=0;--i){
			if(sum[i]>ans){
				last+=(fp[i]+1)*(sum[i]-ans);//sum[i]-ans为突变的个数
				ans=sum[i];
			}
		}
		printf("%lld\n",last-first);
	}
	return 0;
}