2018年蓝桥杯省赛-日志统计

题目

题目链接

题解

贪心，尺取。

首先按照时间从小到大，对输入的每一组 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