题解分享
题解分享简介
日志统计(编程题) - 题解
```
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
#define x first
#define y second
int n,d,k;
int cnt[N];
bool st[N];
typedef pair<int,int> PII;
PII logs[N];
int main()
{
cin>>n>>d>>k;
for(int i=0;i<n;i++)cin>>logs[i].x>>logs[i].y;
sort(logs,logs+n);//时间进行排序
for(int i=0,j=0;i<n;i++)//j是左端点
{
int id=logs[i].y;
cnt[id]++;
while(logs[i].x-logs[j].x>=d)
{
cnt[logs[j].y]--;
j++;
}
if(cnt[id]>=k)st[id]=true;
}
for(int i=0;i<100010;i++)if(st[i])cout<<i<<endl;
return 0;
}
```
查看全文
0
0
0
1
日志统计(编程题) - 题解
```cpp
// https://dashoj.com/d/lqbproblem/p/53
#include <bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll n, d, k;
ll cnt[N];
pll logs[N];
bool ans[N];
int main() {
cin >> n >> d >> k;
for (ll i = 0; i < n; i++) cin >> logs[i].first >> logs[i].second;
sort(logs, logs + n);
for (ll i = 0, j = 0; j < n; j++) {
cnt[logs[j].second]++;
while (logs[j].first - logs[i].first >= d) {
cnt[logs[i].second]--;
i++;
}
if (cnt[logs[j].second] >= k) ans[logs[j].second] = true;
}
for (int i = 0; i < N; i++) if (ans[i]) cout << i << endl;
return 0;
}
```
查看全文
0
0
0
0
日志统计(编程题) - 题解
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define LL long long
#define endl '\n'
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int n, D, K; // n表示日志个数，D表示连续时间，K表示点赞不小于此值就为热帖
PII logs[N]; // 存放日志：某一ts时刻和帖子id
int like[N]; // 存放每个帖子id的点赞数
bool st[N]; // 存放每个帖子id是否为热帖，true是热帖，false不是热帖
void solve()
{
cin >> n >> D >> K;
for (int i = 0; i < n; i++) cin >> logs[i].first >> logs[i].second;
sort(logs, logs + n);
for (int i = 0, j = 0; i < n; i++)
{
int _id = logs[i].second; // 提取每条日志中的帖子id
like[_id]++; // 对应id的帖子点赞数+1
/* 如果某个时刻T不满足该贴在[T, T+D) 这段时间内，去除过期点赞
ts: 0 0 9 10 10 100 100
i
j
↓
ts: 0 0 9 10 10 100 100
i
j
↓
ts: 0 0 9 10 10 100 100
i
j
↓
ts: 0 0 9 10 10 100 100 (进入while，去除过期点赞)
i
j
...
ts: 0 0 9 10 10 100 100 (退出while)
i
j
*/
while (logs[i].first - logs[j].first >= D)
{
like[logs[j].second]--;
j++;
}
if (like[_id] >= K) st[_id] = true; // 符合条件的帖子id将被标记为热帖
}
for (int i = 0; i < 1e5; i++)
if (st[i]) cout << i << endl; // 输出热帖编号
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
```
查看全文
0
0
0
0
