首页 > 其他分享 >寒假每日一题——懒惰的牛

寒假每日一题——懒惰的牛

时间:2023-04-02 18:47:40浏览次数:48  
标签:10 懒惰 int 贝茜 每日 位置 寒假 草地 sum

懒惰的牛

问题描述

这是一个炎热的夏日。

懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置,以便可以在短距离内尽可能多地吃到美味的草。

贝茜所在的田野中共有 N 片草地,我们可以将田野视作一个一维数轴

i 片草地中包含 gi 单位的青草,位置坐标为 xi

不同草地的位置不同。

贝茜想选取田野中的某个点作为她的初始位置(可能是某片草地所在的点)。

只有一片草地与她的初始位置的距离不超过 K 时,贝茜才能吃到那片草地上的草。

如果贝茜选择最佳初始位置,请确定她可以吃到的青草最大数量。

输入格式
第一行包含两个整数 NK

接下来 N 行,每行描述一片草地,包含两个整数 gixi

输出格式
输出如果贝茜选择最佳初始位置,则她可以吃到的青草最大数量。

数据范围

1≤N≤\(10^5\),

1≤gi≤10000,

0≤xi≤\(10^6\),

1≤K≤2×\(10^6\)

输入样例:

4 3
4 7
10 15
2 2
5 1

输出样例:

11

样例解释
最佳初始位置选择为 x=4,可以吃到 x=1,x=2,x=7 处的青草。

思路分析

在这里插入图片描述

完整代码

#include <bits/stdc++.h>
using namespace std;

int n, k;

typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII q[N];
#define x first 
#define y second

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &q[i].y, &q[i].x);
    }
    
    sort(q, q + n);
    int res = 0, sum = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        sum += q[i].y;
        while(q[i].x - q[j].x > 2 * k) sum -= q[j++].y;
        res = max(res, sum);
    }
    
    cout << res << endl;
    return 0;
}

标签:10,懒惰,int,贝茜,每日,位置,寒假,草地,sum
From: https://www.cnblogs.com/i-rong/p/17280966.html

相关文章

  • 寒假每日一题——金发姑娘和N头牛(map+手写离散化)
    金发姑娘和N头牛问题描述你可能听过关于金发姑娘和三只熊的经典故事。然而,鲜为人知的是,金发姑娘最终成了一个农民。在她的农场中,她的牛棚里有N头奶牛。不幸的是,她的奶牛对温度相当敏感。对于奶牛i,使其感到舒适的温度为Ai…Bi。如果金发姑娘将牛棚的恒温器的温度T设置......
  • 寒假每日一题——闪烁(状态压缩)
    闪烁问题描述农夫约翰对牛棚里昏暗的灯光感到不满,刚刚安装了一个新吊灯。新吊灯由N个灯泡组成,这N个灯泡围成一圈,编号为0∼N−1。奶牛对这个新吊灯非常着迷,并且喜欢玩以下游戏:对于第i个灯泡,如果在T−1时刻,它左侧的灯泡(当i>0时,为第i−1个灯泡;当i=0时,为第N−1......
  • 寒假每日一题——困牛排序(思维题)
    困牛排序问题描述FarmerJohn正在尝试将他的N头奶牛,方便起见编号为1…N,在她们前往牧草地吃早餐之前排好顺序。当前,这些奶牛以p1,p2,p3,…,pN的顺序排成一行,FarmerJohn站在奶牛p1前面。他想要重新排列这些奶牛,使得她们的顺序变为1,2,3,…,N,奶牛1在FarmerJohn旁......
  • 寒假每日一题——大型植被恢复
    大型植被恢复问题描述长时间的干旱使得FarmerJohn的N块草地上牧草匮乏。随着雨季即将到来,现在应当是重新种植的时候了。在FarmerJohn的储物棚里有四个桶,每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农,FarmerJohn想要确保他的每头奶......
  • leetcode 739.每日的温度 Java
    739.每日的温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0来代替。示例1:输入:temperatures=[73,74,75,71,69,72,76,73]输出:[1,1,4,2,1,......
  • 算法随想Day51【单调栈】| LC739-每日温度、LC496-下一个更大元素Ⅰ
    LC739.每日温度vector<int>dailyTemperatures(vector<int>&temperatures){intsize=temperatures.size();vector<int>result(size,0);vector<int>sta;sta.push_back(0);for(inti=1;i<size;++i){......
  • 每日总结2023-04-01
    今天完成了部分界面并修改了部分之前的界面成果:广告收益界面,LIstView中没有数据,暂时没有显示第二个界面用于车主添加产品类别,登记种类和数量第三个界面美化第四个界面为设备绑定界面 ......
  • 2023/04/01每日总结
    今天学习html,发现web页面不会做,现在从头开始学。准备做一个课表 ......
  • 每日总结--2023/3/31(解决了数据库连接不正常的问题,完成了javaweb暂时的配置)
    今天耗费一天的时间总算是找到了问题所在.问题出在mysqlServlet的版本上。在重装系统前,我所装的mysqlSevlet版本是5.0左右的,所以连接数据库的驱动也是5.0,包括url,而在重装系统后我的mysqlSevlet版本是8.0以上的,所以用原来的语句是不正确的,要修改为8.0版本的才能够运行,同......
  • 每日总结--2023/3/29(解决sevlet报错问题和数据库中文编码错误)
    今日完成:昨天的残留问题,查询了很多资料,也没能完全解决。首先是tomcat版本问题,重新下载并且部署了tomcat10版本的内容,解决了sevlet代码报错的问题。但是连接数据库仍然是不成功,报500错误,检查了mysql数据库,发现数据库正常(除中文变为?的bug)。连接数据库暂时仍不成功,但是成功解决......