UVA10148- Advertisement（区间选点）

题意：一段路上，给出n个慢跑者跑步的区间，给出k，要求让每个慢跑者都能看到k个广告，区间都是整数操作，也就是说一个广告只能放在一个整数上，求最小贴的广告数

思路：关于区间选点的问题。把所有区间按Ｂ从小到大排序（Ｂ相同时Ａ从大到小排序），则如果出现区间包含的情况，小区间一定排在前面。所以贪心的策略就是，从后往前取k个点。因为只有从后面开始取点，满足的区间才最会最多，这样就能达到使用最少的点的目的。注意如果区间长度小于k的话，区间内所有点都要取到。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 10000;

struct jogger{
    int A, B;
}p[MAXN];

int vis[MAXN * 2 + 5];
int k, n, cnt;

int cmp(jogger a, jogger b) {
    if (a.B != b.B)
        return a.B < b.B;
    return a.A > b.A;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d %d", &k, &n); 
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &p[i].A, &p[i].B); 
            p[i].A += MAXN;
            p[i].B += MAXN;
            if (p[i].A > p[i].B)
                swap(p[i].A, p[i].B);
        }

        cnt = 0;
        memset(vis, 0, sizeof(vis));
        sort(p, p + n, cmp); 
        for (int i = 0; i < n; i++) {
            if (p[i].B - p[i].A <= k - 1) {
                for (int j = p[i].A; j <= p[i].B; j++) 
                    if (!vis[j]) {
                        vis[j] = 1; 
                        cnt++; 
                    }  
            }
            else {
                int temp = 0;         
                for (int j = p[i].A; j <= p[i].B; j++) 
                    if (vis[j])
                        temp++;
                if (temp >= k) 
                    continue;
                for (int j = p[i].B; j >= p[i].A; j--) {
                    if (!vis[j]) {
                        vis[j] = 1; 
                        cnt++;
                        temp++;
                    }                 
                    if (temp >= k)
                        break;
                }
            }
        }

        printf("%d\n", cnt);
         for (int i = 0; i < MAXN * 2 + 5; i++)
             if (vis[i] && cnt) {
                 printf("%d\n", i - MAXN); 
                 cnt--;
             }
         if (cas)
             printf("\n");
    }
    return 0;
}

UVA10148- Advertisement（区间选点）,布布扣,bubuko.com

UVA10148- Advertisement（区间选点）

原文：http://blog.csdn.net/u011345461/article/details/38341641