2018年蓝桥杯C/C++ B组省赛试题H：日志统计题解

梦里梦外; 2022-12-28 14:18 165阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
 *  解题思路
 *  解题代码

--------------------

# 题目描述 #

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：

`ts id`

表示在ts时刻编号id的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。

具体来说，如果存在某个时刻T满足该帖在\[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。

给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

## 输入格式 ##

> 第一行包含三个整数N、D和K。  
> 以下N行每行一条日志，包含两个整数ts和id。

> 对于50%的数据，1 <= K <= N <= 1000  
> 对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000

## 输出格式 ##

> 按从小到大的顺序输出热帖id。每个id一行。

## 输入样例 ##

7 10 2 
    0 1 
    0 10 
    10 10 
    10 1 
    9 1
    100 3 
    100 3

## 输出样例 ##

1
    3

# 解题思路 #

用二维数组存放每个帖子`id`所对应的哪个时刻被点赞过，即`vector<int> v[100005]`

用 **尺取法** 的思想，固定长度`D`来从头遍历到尾部，只要存在一次尺子`D`中不少于`k`次点赞，就说明是热帖

*  小剪枝：如果一个帖子点赞数都没有k个，那么肯定不会是热帖。即`v[i]`的长度`v[i].size() < k`

# 解题代码 #

//
    //  main.cpp
    //  2018lanqiao-h
    //
    //  Created by 陈洋 on 2020/10/13.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    vector<int> v[100005];
    int n,d,k;
    int main(int argc, const char * argv[]) {
        
        cin >> n >> d >> k;
        
        int ts,id;
        int max = 0;    //统计最大的id号用于遍历
        
        for(int i = 0; i < n; i++){
        
            cin >> ts >> id;
            if(max < id)
                max = id;
            v[id].push_back(ts);
        }
        
        for(int i = 0; i <= max; i++){
        
            if(v[i].size() < k)
                continue;
            
            sort(v[i].begin(), v[i].end());
            
          	//尺取法
            for(int j = 0; j < v[i].size() - k + 1; j++){
        	
                if(v[i][j + k - 1] - v[i][j] < d){
        
                    cout << i << endl;
                    break;
                }
            }
          	//尺取法
        }
        
        return 0;
    }