【蓝桥杯省赛真题】日志统计

标题：日志统计

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

【输入格式】 第一行包含三个整数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 资源约定： 峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 1000ms

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

这道题比赛的时候我是没有做出来的，我想到用vector排序了然后又想到优先队列什么的，然后发现因为它是要看“任一个区间”，而且数据量还挺大的，我觉得暴力也烦（当然，如果暴力了能骗到分则是好的！！！），就没写。

看了个解析，原来方法是“尺取法”。如果我早先了解了这个方法，这道题就迎刃而解了（所以还需要多学方法和应用练习！）

思路：因为观察到输入里面一个事件id可以有多个时间，所以就用vector来存对应的多个时间——vector型数组！（god，当时真没想到vector型数组。。。T T）。然后对于每一个事件，把时间排好序，去它的vector里面根据题意用尺取法就好了。

代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int n,d,k;
const int maxn=1e5+5;
vector<int> thing[maxn];

bool judge(int id)
{
	int len=thing[id].size();
	if(len<k)
		return false;
	sort(thing[id].begin(),thing[id].end());
	int start=0;int end=0;
	int cnt=0;
	while(start<=end && end<len)
	{
		cnt++;  
		if(cnt==k)  // 窗口长度为k时，开始讨论移动指针，从而滑动窗口
		{
			if(thing[id][end]-thing[id][start]<d) //注意是小于(题中说是前闭后开区间 
				return true;
			else  //如果if语句不成立，那么你再去后移end也是不符要求的，所以需要向后滑动窗口
			{
				cnt--;
				start++; 
			} 
		}
		end++;  // 刚开始只有end在移动，是为了让窗口长度达到k；长度为k的窗口若不满足题意条件，则通过start和end同时移动来向后滑动窗口
	} 
	return false;
}  

int main()
{
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++)
	{
		int ts,id;
		cin>>ts>>id;
		thing[id].push_back(ts);
	}

    int n_things = thing.size(); //取vector的长度，即有多少个id
    for(int id=1;id<=n_things;id++)
    {
        if(judge(id))
            cout<<id<<endl;
    }
    return 0;
}

关于“尺取法”，我的理解：

（1）啥情况适合用尺取法：涉及“（寻找任一个）区间”。

（2）想清楚两个点：①针对题意，怎么找到这个区间，即这个区间应满足怎样的条件。②关于start和end标识，什么时候start++，什么时候end++，什么时候应该跳出循环。anyway，要好好分析题意，结合题意设计。