ECNU 3263 丽娃河的狼人传说（贪心）

链接：http://acm.ecnu.edu.cn/problem/3263/

题意：

从 1 到 n 的一条数轴。有 m 个区间至少要安装一定数量的路灯，路灯只能装在整数点上，有k盏路灯已经安装好，现在求最少需要安装多少盏路灯。

分析：

一开始我的想法是按重叠部分给数轴每个整数点一个优先级，然后在区间中优先度高的先补灯。但比赛中无论如何都是WA，最后找出错误是因为这样补灯优先级相同时候他会按顺序补灯。

最后看题解发现他是根据右端点升序排序进行处理，然后不满足的话尽量往右边补灯，因为如果按右端点排序，那么每一个区域的左边肯定先被前一个区域考虑到了。

给出两组组数据，第一组证明我第一个想法是错误的，第二组测试。

8 3 1

1 6 2

1 3 1

4 6 1

答案是：2
9 5 6
1 2 3 4 5 7
1 5 4
4 8 5
1 3 3
2 9 7
1 8 3

答案是：2

#include<bits/stdc++.h>

using namespace std;

const int maxn =  1e4;

struct K

{

    int x, y, num;

    friend bool operator < (K a, K b)

    {

        return a.y < b.y;

    }

};

K ins[1000];

bool lap[maxn];

int n,m,k,ans,flag;

int main()

{

//    freopen("1.txt","r",stdin);

    int t;

    scanf("%d", &t);

    for(int kase = 1; kase <= t; kase ++)

    {

        memset(lap,0,sizeof(lap));

        scanf("%d %d %d", &n, &m, &k);

        for(int i = 0; i < k; i++)

        {

            int t;

            scanf("%d", &t);

            lap[t] = 1;

        }

        for(int i = 0; i < m; i++)

        {

            scanf("%d %d %d", &ins[i].x, &ins[i].y, &ins[i].num);

        }

        sort(ins, ins+m);

        ans = 0,flag = 0;

        for(int i = 0; i < m; i++)

        {

            int b = ins[i].x, e = ins[i].y, need = ins[i].num;

            int sum = 0;

            for(int j = e; j >= b; j--)

            {

                if(lap[j])

                {

                    sum++;

                }

            }

            int pos = e;

            while(sum < need && pos >= 1)

            {

                if(!lap[pos])

                {lap[pos] = 1;

                    sum++;

                    ans++;

                }

                pos--;

            }

            if(sum < need)

            {

                flag = 1;

                break;

            }

        }

        if(flag) printf("Case %d: -1\n",kase);

        else printf("Case %d: %d\n",kase,ans);

    }

}

巴特西

ECNU 3263 丽娃河的狼人传说（贪心）

链接：http://acm.ecnu.edu.cn/problem/3263/

题意：

分析：

最新文章

热门文章

巴特西

ECNU 3263 丽娃河的狼人传说 （贪心）

链接：http://acm.ecnu.edu.cn/problem/3263/

题意：

分析：

最新文章

热门文章

ECNU 3263 丽娃河的狼人传说（贪心）