uva 10148 - Advertisement

点击打开链接uva 101148

题目意思：

公园里有一个广告牌，由于公园里经常有很多人在慢跑锻炼身体，现在有一个客户想在这个广告牌上面贴广告，他想让每一个慢跑的人都能够看到至少k个广告，由于每一个人跑步的路径不同，不同人看到的广告是不同的，可能只看到一个广告。现在规定广告是一序列连续的整数表示，有n个人，每一个能够看到的第一个广告和最后一个广告是已知的，现在要求满足这个客户的要求下（客户要求了要尽量省钱），找到最少需要贴广告的数量，并输出所贴的广告的编号 。

解题思路：

1思路：贪心

2分析：区间选点的变形题，由原来的选一个点变成现在选5个点，其它类似

3区间选点问题 ：
       1解题过程：将每个线段按照终点坐标进行递增排序，相同终点的前点坐标大的在前面，一个个将其满足

       2贪心证明:要想使得剩下的线段上选择的点最少，那么就应该尽量使得已经选择了的点尽量能在后面的线段中发挥作用，而我们是从左往右选择线段的，那么要使得选取的点能满足后面线段的要求，那么必须是从线段的有端点开始选点，那么问题(2)一样涉及到一个问题，如果是按照线段的左端点对线段进行排序的话，不知道右端点的话，每一条线段都不能对之前已经操作过的所有线段进行一个总结，那么这就同样不满足贪心算法的最优子结构性质了

4解题过程：1首先对输入数据进行输出，让小的数据在第一个  2对这些区间按照Bi进行升序排序   3对这些区间进行扫描，假设当前的额区间为[Ai , Bi],那么我们必须先算出这个区间内的点出现过的个数num，如果num大于等于k那么之接跳过；否则还要在这个区间选取k-num个数，根据区间选点的性质则我们从Bi往前枚举如果当前的值为j没有被选那么就要选取这个点；依次直到枚举完所有的区间即可

5注意事项：用set来存储点，默认使用“<”进行排序。但是效率低，AC用了2.100s。

代码：

#include <algorithm>  
#include <iostream> 
#include <cstring>
#include <cstdio> 
#include <set>
using namespace std;
#define MAXN 1010

int t;
int k , n;
struct path{
    int first;
    int last;
}p[MAXN];
set<int>s;
/*自定义cmp函数*/
bool cmp(path p1 , path p2){
    if(p1.last < p2.last) return true;
    return false;
}

void solve() {
    int i , j , cnt;
    int num ,  tmp;
    ans = 0 ; s.clear() ;
    sort(p , p+n , cmp);/*快速排序*/
    set<int>::iterator it;
    for(i = 0 ; i < n ; i++){/*枚举n个区间*/
        num = 0;
        for(j = p[i].last ; j >= p[i].first ; j--){/*求出num*/
            it = s.find(j);
            if(it != s.end()) num++;
        }
        tmp = p[i].last - p[i].first + 1;
        if(num >= k || num == tmp) continue;/*num大于等于k跳过*/
        if(tmp > k) tmp = k;/*tmp为区间的长度，如果长度大于k则只要长度为k即可*/
        for(j = p[i].last , cnt = 0 ; cnt < tmp-num ; j--){/*从后往前推*/
            it = s.find(j);
            if(it == s.end()){
               s.insert(j) ; cnt++;
            }
        }
    }
}
/*输出set*/
void output(){
    printf("%d\n" , s.size());
    set<int>::iterator it;
    for(it = s.begin() ; it != s.end() ; it++)
        printf("%d\n" , *it);
}

int main() {
    //freopen("input.txt", "r", stdin);
    int a , b;
    scanf("%d%*c" , &t);
    while(t--){
         scanf("%d%d%*c" , &k , &n);       
         for(int i = 0 ; i < n ; i++){
             scanf("%d%d" , &a , &b);
             if(a < b){ p[i].first = a ; p[i].last = b; }
             else{ p[i].first = b ; p[i].last = a; }
         }
         solve() ; output();
         if(t) printf("\n");
    }
    return 0;
}