蓝桥杯2018年第九届真题-日志统计-题解（C++代码）官方题解

解题思路:每一步都标记的很清晰，快读和快输出得用，因为原题数据很大

注意事项:对于50%的数据，1 <= K <= N <= 1000   
               对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
参考代码:

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int i,j,ans,n,k,m,x,y;

inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

struct T{
        int a,b;//分别为是时刻和ID存储在vector中
};
bool cmp(T a,T b){//自定义排序，按照时刻做升序排序
        return a.a<b.a;
}
int N,D,K;
int main()
{
       std::ios::sync_with_stdio(0);
       cin.tie(0);
       cout.tie(0);//以上为快读
       cin>>N>>D>>K;
       vector<T> c(N);//存日志数据  ，初始为N大小
       map<int, int> cnt;//记录ID及出现的次数
      for(i=0;i<N;i++){//读取数据
           cin>>c[i].a>>c[i].b;//分别放在vector中
      }
      sort(c.begin(),c.end(),cmp);//自定义排序，对vector排序
      int j=0;//往后探的指针-尺取法
     set<int> answers;//记录结果ID，自然有序（set的好处）
     for(i=0;i<N;i++){//i是起点
          while(j<N&&c[j].a-c[i].a<D){//j时刻减i时刻小于D
                   cnt[c[j].b]++;//该id的计数+1
                   if(cnt[c[j].b]>=K)//如果满足条件
                        answers.insert(c[j].b); //放入答案里
                   j++;//往后移
           }
      cnt[c[i].b]--;//上一个区间，b的计算扣除，不干扰下一个区间
    }
    for(set<int>::iterator i=answers.begin();i!=answers.end();i++){//迭代器遍历输出
    //cout<<*i<<endl;这样会超时
    write(*i);
    printf("\n");
    }
    return 0;
}