标题:日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有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
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时,注意选择所期望的语言类型和编译器类型。
这道题用到了一个尺取法,尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。
首先借助一道其他题目来说一下尺取法。
题意:给定一个序列,使得其和大于或等于S,求最短的子序列长度。
分析:首先,序列都是正数,如果一个区间其和大于等于S了,那么不需要在向后推进右端点了,因为其和也肯定大于等于S但长度更长,所以,当区间和小于S时右端点向右移动,和大于等于S时,左端点向右移动以进一步找到最短的区间,如果右端点移动到区间末尾其和还不大于等于S,结束区间的枚举。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 #define LL long long 6 const int maxn=1e5+5; 7 #define INF 0x3f3f3f3f 8 9 LL a[maxn]; 10 int n,t,ans=INF; 11 LL sum,s; 12 13 int main(){ 14 cin>>t; 15 while(t--){ 16 cin>>n>>s; 17 for( int i=0; i<n; i++ ){ 18 cin>>a[i]; 19 } 20 int st=0,en=0; 21 ans=INF; 22 sum=0; 23 while(1){ 24 while(en<n&&sum<s) sum+=a[en++]; 25 if(sum<s) break; 26 ans=min(ans,en-st); 27 sum-=a[st++]; 28 } 29 if(ans==INF) ans=0; 30 cout<<ans; 31 } 32 return 0; 33 }
大致了解了尺取法,利用vector型的数组这道题也就很简单了。。。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 using namespace std; 5 const int maxn=1e5+5; 6 int n,d,k; 7 vector<int> journal[maxn]; 8 9 void judge(vector<int>& vec,int id){ 10 int Size=vec.size(); 11 if(Size<k) return ;//点赞条数小于k,肯定不能上热帖 12 sort(vec.begin(),vec.end()); 13 int st=0,en=1; 14 int cnt=0; 15 while(st<=en&&en<Size){ 16 if(vec[en]-vec[st]<d){ 17 cnt=max(cnt,en-st+1); 18 en++; 19 } 20 else{ 21 st++; 22 } 23 } 24 // cout<<"cnt="<<cnt<<" "; 25 26 if(cnt>=k){ 27 cout<<id<<endl; 28 } 29 } 30 int main(){ 31 cin>>n>>d>>k; 32 for( int i=0; i<n; i++ ){ 33 int ts,id; 34 cin>>ts>>id; 35 journal[id].push_back(ts); 36 } 37 for( int i=0; i<maxn; i++ ){ 38 judge(journal[i],i); 39 } 40 41 return 0; 42 }