首页 > 代码库 > cogs 1682. [HAOI2014]贴海报 WW

cogs 1682. [HAOI2014]贴海报 WW

2024-09-26 04:18:40   223人阅读

★★☆   输入文件：ha14d.in   输出文件：ha14d.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下：

1．electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；

2．所有张贴的海报的高度必须与electoral墙的高度一致的；

3．每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；

4．后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。

【输入格式】

第一行：     N   M            分别表示electoral墙的长度和海报个数

接下来M行:   Ai   Bi          表示每张海报张贴的位置


【输出格式】

输出贴完所有海报后，在electoral墙上还可以看见的海报数。

【样例输入】


100 5

1 4

2 6

8 10

3 4

7 10


【样例输出】

4

【提示】


技术分享

【约束条件】

1 0<= N <= 10000000     1<=M<=1000   1<= Ai <= Bi <=10000000

所有的数据都是整数。数据之间有一个空格

 

正解树状数组（线段树？？？），暴力52分（cogs），AC(luogu):

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<string>
 7  
 8 using namespace std;
 9 const int N=10000010;
10  
11 inline int read()
12 {
13     int x=0,f=1;
14     char c=getchar();
15     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
16     while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();
17     return x*f;
18 }
19  
20 int vis[N];
21  
22 int main()
23 {
24     
25     freopen("ha14d.in","r",stdin);
26     freopen("ha14d.out","w",stdout);
27     int n=read();
28     int m=read();
29     for(int i=1;i<=m;i++)
30     {
31         int u=read();
32         int v=read();
33         for(int j=u;j<=v;j++)
34         {
35             vis[j]=i;
36         }
37     }
38     int Answer=0;
39     for(int i=1;i<=m;i++)
40     {
41         bool flag=1;
42         for(int j=1;j<=n&&flag;j++)
43         {
44             if(vis[j]==i)
45             {
46                 Answer++;
47                 flag=0;
48             }
49         }
50     }
51     
52     printf("%d",Answer);
53     
54     return 0;
55 }

 

cogs 1682. [HAOI2014]贴海报 WW


联系
我们