AcWing 1238. 日志统计
原题链接
中等
作者:
大海呀大海
,
2020-07-10 20:17:11
,
所有人可见
,
阅读 10709
双指针算法
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 100010;
int n, d, k;
PII logs[N];
bool st[N];
int cnt[N];
int main(){
scanf("%d%d%d", &n, &d, &k);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &logs[i].x, &logs[i].y);
sort(logs, logs + n);
for (int i = 0, j = 0; i < n; i ++ ){
int t = logs[i].y;
cnt[t] ++;
while (logs[i].x - logs[j].x >= d){
cnt[logs[j].y] --;
j ++;
}
if (cnt[t] >= k) st[t] = true;
}
for (int i = 0; i <= 100000; i ++ ) if (st[i]) cout << i << endl;
return 0;
}
有趣的刷题生活从看到这篇有趣的题解开始~
这里的i时刻和j时刻应该不是准确的说法 思路是利用i和j遍历日志,因为时间是从小到大排序的,所以让j从头开始,不断遍历i下标的日志,如果j和i指向的时间差大于D了就让j移动直到满足时间差的关系,而移动j势必有日志要移出区间,于是先删再移 这里可以思考一下while循环和最后if判断的顺序问题 可以帮助更好的理解过程
while (logs[i].x - logs[j].x >= d)我不理解他是怎么确定 i 和 j 的id相同
i和j的id不需要相同。你首先得知道他是如何枚举的。它是枚举每个时间段,在符合条件的时间段里,说白了就是小于等于d的时间段里,去统计每个id的数量,如果一个id的数量大于k,就是热帖。由于时间段是不断向后枚举的,所以当时间段大于了d,就必须抛弃原时间段开头的那个元素,因此有这句代码:cnt[logs[j].y] –; ~~~ 半个月没刷题了 今天开始复习蓝桥杯 冲冲省二
大佬 我似乎终于懂了
我觉得这里t一次循环只能确定一个id啊,万一有那种同一时刻很多id点赞的情况,他这样不会错过别的id吗?因为i直接++了到下一时刻。大佬能解答一下吗…
我理解的是,因为按照时间排序的日志,并且D相同,现在的时间段如果不满足遍历到的日志时间的话,那前面的也过了有效时间,可以舍弃。如果前面的有某个id到了点赞数k,而i是从前面每个日志遍历来的,在遍历那个日志的时候肯定被统计过了,所以是可以用双指针的。你说的同一时刻很多id,那i和j指向的时间段是不变的吧
谢谢,当时没看懂,过了一段时间再看,一下就通了。
#### 贴一个单调队列的。
#include <iostream> #include <set> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 100010; int n, d, k; int q[N], hh = 0, tt = -1; int zhan[N]; PII ts[N]; set<int> res; int main() { cin >> n >> d >> k; for(int i = 0; i < n; i ++) cin >> ts[i].first >> ts[i].second; sort(ts, ts + n); //遍历所有点赞的帖子 for(int i = 0; i < n; i ++) { while(ts[q[hh]].first <= ts[i].first - d && hh <= tt){ hh ++; zhan[ts[q[hh]].second] --; } zhan[ts[i].second] += 1; if(zhan[ts[i].second] >= k) res.insert(ts[i].second); q[++tt] = i; } for(auto i : res) cout << i << endl; return 0; }
你这个过不了啊
我的电脑可以过的
你说的好好笑
#include <iostream> #include <set> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 100010; int n, d, k; int q[N], hh = 0, tt = -1; int zhan[N]; PII ts[N]; set<int> res; int main() { cin >> n >> d >> k; for(int i = 0; i < n; i ++) cin >> ts[i].first >> ts[i].second; sort(ts, ts + n); //遍历所有点赞的帖子 for(int i = 0; i < n; i ++) { while(ts[q[hh]].first <= ts[i].first - d && hh <= tt){ zhan[ts[q[hh ++]].second] --; } zhan[ts[i].second] += 1; if(zhan[ts[i].second] >= k) res.insert(ts[i].second); q[++tt] = i; } for(auto i : res) cout << i << endl; return 0; }
上面那个hh++不应该单独列出来,应该从hh开始。现在这个是对的
感谢大佬,注释也很可爱
#include<bits/stdc++.h> #define PII pair<int,int> #define id first #define t second using namespace std; const int N = 100005; int n,d,k; PII p[N]; bool vis[N]; int main() { cin>>n>>d>>k; for(int i=1;i<=n;i++) cin>>p[i].t>>p[i].id; sort(p+1,p+n+1); for(int i=1,j=1;i<=n&&j<=n;i++){ if(vis[p[i].id]) continue; while(p[i].id!=p[j].id&&j<i) j++; while(p[i].t-p[j].t+1>d&&j<i) j++; if(p[i].t-p[j].t+1<=d&&i-j+1>=k&&!vis[p[i].id]){ cout<<p[i].id<<endl; vis[p[i].id]=true; } } return 0; }
为什么foe循环里面是while循环而不是if判断呀
每个i都需要通过起始的j不断移动来判断
为啥过不了啊
#include<bits/stdc++.h> using namespace std; //1238 日志统计 const int N=1e5+10; int n,d,k; multiset<int>se;//存某个区间某个id出现的次数 map<int,int> mp;//存在几个区间符合要求 struct Range { int ts,id; bool operator<(const Range &W) { return ts<W.ts; } }rang[N]; int main() { cin>>n>>d>>k; for(int i=0;i<n;i++) { int t,id; cin>>t>>id; rang[i]={t,id}; } sort(rang,rang+n); int i=0,j=0; while(i<n) { //走一个区间 while(rang[j].ts<rang[i].ts+d&&j<n) { int t=rang[j].id; j++; se.insert(t); if(se.count(t)>=k) { mp[t]++; } } se.clear(); i=j; } for(auto t=mp.begin();t!=mp.end();t++) { if(t->second) cout<<t->first<<endl; } }
注释里应该是在
i
时刻这里是一些关于不懂为什么只用j就能实现维护区间的一些解释,希望给大家提供帮助
https://www.acwing.com/solution/content/276107/
这题能否用滑动窗口来实现呢?
这不就是滑动窗口吗
懂啦!谢谢大佬 好生动的注解
#include[HTML_REMOVED]
using namespace std;
int main() {
int N, D, K;
cin >> N >> D >> K;
unordered_map<int, vector<int>> likes; // 记录每个帖子在每个时刻的点赞数 for (int i = 0; i < N; i++) { int ts, id; cin >> ts >> id; likes[id].push_back(ts); // 更新帖子的点赞数 } vector<int> hot_posts; // 记录曾是热帖的帖子编号 for (auto& p : likes) { vector<int>& timestamps = p.second; sort(timestamps.begin(), timestamps.end()); // 将时间戳按升序排序 int left = 0, right = 0; // 左右指针,表示时间段的左右边界 int count = 0; // 计数器,统计点赞数 while (right < timestamps.size()) { // 计算当前时间段内的点赞数 if (timestamps[right] - timestamps[left] < D) { count++; right++; } else { // 如果时间段超过了 D,则移动左指针 count--; left++; } // 如果当前时间段内的点赞数达到了 K,则该帖子是热帖 if (count >= K) { hot_posts.push_back(p.first); break; } } } sort(hot_posts.begin(), hot_posts.end()); // 对热帖编号进行排序 for (int id : hot_posts) { cout << id << endl; // 输出热帖编号 } return 0;
}
看起来就是滑动窗口
哈希表存储遍历时间
#include <iostream> #include <cstdio> #include <algorithm> #include <set> #include <vector> using namespace std; const int N = 100010; int n, d, k; int t[N]; int cnt[N]; int main() { vector<vector<int>> hash(N); scanf("%d%d%d", &n, &d, &k); int len = 0; for (int i = 0 ;i < n; i ++) { int t, id; scanf("%d%d", &t, &id); hash[t].push_back(id); len = max(len, t); } set<int> s; for (int l = 0, r = 0; r <= len; r ++) { for (int j = 0; j < hash[r].size(); j ++) { int id = hash[r][j]; //cout << id << endl; cnt[id]++; if (cnt[id] >= k) s.insert(id); } while (r - l + 1 >= d) { for (int j = 0; j < hash[l].size(); j ++) { int id = hash[l][j]; cnt[id]--; } l ++; } } for (auto it = s.begin(); it != s.end(); it ++) { printf("%d\n", *it); } return 0; }
看上去两层循环,时间复杂度应该是o(n),就是把所有事件都遍历了两遍
大佬帮忙看看,为什么用加法过不了这题啊
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int n,d,k;
int cnt[N];
bool st[N];
#define ts first
#define id second
pair[HTML_REMOVED]g[N];
int main()
{
scanf(“%d%d%d”,&n,&d,&k);
for(int i=1;i<=n;i)
{
scanf(“%d%d”,&g[i].ts,&g[i].id);
}
sort(g+1,g+n+1);//直接对时间进行排序,然后只统计在这段时间内每种id的点赞数就行了
printf(“排序后\n”);
for(int i=1;i<=n;i)
{
printf(“%d %d\n”,g[i].ts,g[i].id);
}
for(int i=1,j=1;i<=n;i)
{
memset(cnt,0,sizeof cnt);
printf(“gg\n”);
while(g[j].ts-g[i].ts[HTML_REMOVED]= k) st[g[j].id] = true;
j;
}
if (cnt[g[j].id] >= k) st[g[j].id] = true;
}
for (int i = 0; i < 100010; i++) if (st[i]) printf("%d\n", i); return 0;
}
你把你代码放到两组三个点之间,就能格式化显示
#include<bits/stdc++.h> using namespace std; #define x first #define y second const int N=100010; typedef pair<int,int> PII; int n,d,k,res,sum[N]; PII p[N]; bool q[N]; int main() { cin >> n >> d >> k; for (int i = 1; i <= n; i++) { scanf("%d %d",&p[i].y,&p[i].x); sum[p[i].x]++; } sort(p + 1, p + n + 1); for (int i = 1, j = 1; i <= n;) { res = 0; if (sum[p[i].x] >= k && !q[p[i].x]) { while (p[i].x==p[j].x&&j <= n && p[j].y - p[i].y <= d - 1) { res++; if (res == k) { q[p[i].x] = true; printf("%d\n",p[i].x); break; } j++; } } j=++i; } return 0; }
谁可以优化一下我的代码,我是枚举的id,最后一组数据超时了
懂了 tql
这里为啥i是走前面,j是走后面?,i不是后指针吗,j才是前指针吧,如果while循环里面条件满足,不是j就往后走一步吗
在这里,题意说是左闭右开
[i,i+k)
,包含为k,但是在这里转化为了左闭右闭[j,i]
,i-j<=k-1,同样包含k个时间点nb!!!