题目链接
题解贪心,尺取。
首先按照时间从小到大,对输入的每一组 t s ts ts和 i d id id进行排序;
遍历每一对,取当前这对的
t
s
ts
ts作为题目中的
T
T
T,让另一个指针不断地向前走,直到指针所指的对的
t
s
ts
ts大于等于了
T
+
D
T+D
T+D就停止向前走,指针所经过的全部对的
i
d
id
id都在
[
T
,
T
+
D
)
[T,T+D)
[T,T+D)内,所以用cnt[i]
表示第i
个文章在
[
T
,
T
+
D
)
[T,T+D)
[T,T+D)内被点赞的数量,如果数量大于
K
K
K,则说明找到一个答案;指针到头了,我们的遍历就可以再进一步了,再以下一个对的
t
x
tx
tx为
T
T
T重复,注意当指针走完之后,遍历进一步之前,时间起点要后移了,所以要把遍历到的这个文章移出去,也就是cnt
要减少。
#include
using namespace std;
const int N = 1e5+10;
int n, D, K, cnt[N];
vector ans;
struct node {
int ts, id;
} a[N];
bool cmp (node a, node b) {
return a.ts > n >> D >> K;
for (int i = 0;i > a[i].ts >> a[i].id;
sort (a, a+n, cmp);
for (int i = 0, j = 0;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?