NKOI Round 5 2.工厂

NKOI Round 5 2.工厂

​​ 2.工厂（factory.cpp/c/pas） 【问题描述】 工厂中有一条生产线，包含排成一排的 n个机器，从 1 到 n顺次编号。 工人们需要生产 m 个零件，生产每个零件都需要使用连续的一些机器。 由于机器效率低下，每天每个机器最多只能使用一次。 工人们想要知道一天最多能生产的零件数量。 【输入数据】 第一行一个正整数 T，表示数据组数。 对于每组数据： 第一行两个正整数 n、m。 接下来 m 行，第 i 行两个正整数 L、R，表示生产第 i 个零件需要使用编号在 [L,R]之间的机器。 【输出数据】 一行一个整数表示答案。 【输入输出样例 1】 factory.in factory.out 1 6 3 1 3 2 4 5 6 2 【输入输出样例 2】 factory.in factory.out 2 10 5 1 5 2 3 5 8 7 9 10 10 1000 2 10 20 100 200 3 2

【数据规模和约定】 测试点编号 n m 所有数据 m 的和 1 <=10 <=5 <=1000 2 <=100 <=10 3 <=100000 <=15 4 <=10^9 <=20 <=100 5 <=100 <=1000 6 <=1000 <=10000 7 <=5000 <=20000 8 <=50000 <=200000 9 <=100000 <=500000 10 对于 100%的测试点：1<=n<=10^9，1<=m<=100000，1<=所有数据 m 的和 <=500000

#include#include#include#include#define pa pair#define M 110000using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int l,r;}q[M];stack st;int T,n,m;bool visit[M];inline bool cmp(node a,node b){return a.lq[i].r) st.pop();st.push(make_pair(q[i].r,i)); } while (!st.empty()) visit[st-().second]=true,st.pop();int cnt=0;int now=0; for (int i=1;i<=m;++i){ if (q[i].l>now&&visit[i]) ++cnt,now=q[i].r; } printf("%d\n",cnt); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。