NEERC 1999 Advertisement /// oj22646

题目大意：

输入k，n ；k为每位慢跑者最少应看到的广告牌数

接下来n行描述第 i 位慢跑者的途径路段

输出需要设立的广告牌数接下来每行为设立地点

Sample Input

5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21

Sample Output

19
-5
-4
-3
-2
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27

题解：https://blog.csdn.net/shuangde800/article/details/7828537

#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<stdlib.h>

#include<cstring>

using namespace std;

struct num

{

    int a,b;

    bool operator<(const num& p)const {

        return b<p.b;

    };

}jog[];

bool vis[];

int main()

{

    int n,k;

    while(~scanf("%d%d",&k,&n))

    {

        int st=,ed=,ans=;

        for(int i=;i<n;i++)

        {

            int p,q; scanf("%d%d",&p,&q);

            jog[i].a=min(p,q)+;

            jog[i].b=max(p,q)+;

            st=min(st,jog[i].a);

            ed=max(ed,jog[i].b);

        }

        sort(jog,jog+n);

//        for(int i=0;i<n;i++)

//            printf("%d %d %d\n",jog[i].a-10000,jog[i].b-10000,jog[i].b-jog[i].a);

        memset(vis,,sizeof(vis));

        for(int i=;i<n;i++)

        {

            int len=jog[i].b-jog[i].a+;

            if(len<=k)

            {

                for(int j=jog[i].a;j<=jog[i].b;j++)

                    if(!vis[j]) vis[j]=,ans++;

            }

            else

            {

                int cnt=;

                for(int j=jog[i].a;j<=jog[i].b;j++)

                    if(vis[j]) cnt++;

                if(cnt>=k) continue;

                for(int j=jog[i].b;j>=jog[i].a;j--)

                    if(!vis[j])

                    {

                        vis[j]=; cnt++; ans++;

                        if(cnt>=k) break;

                    }

            }

        }

        printf("%d\n",ans);

        for(int i=st;i<=ed;i++)

            if(vis[i]) printf("%d\n",i-);

        printf("\n");

    }

    return ;

}

巴特西

NEERC 1999 Advertisement /// oj22646

最新文章

热门文章