题解 | #万万没想到之抓捕孔连顺#

万万没想到之抓捕孔连顺

https://www.nowcoder.com/practice/c0803540c94848baac03096745b55b9b

代码思路:
双指针 + 组合数
定义j指针,遍历a[j] - a[i] <= d,就是当前第一个在i位置得到最远能到的j位置,再从i + 1 到 j中选两个位置
//双指针算法
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, mod = 99997867;
ll a[N];
ll n, d;
int main(){
    cin >> n >> d;
    ll ans = 0;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0, j = 0; i < n; i ++){
        while(j + 1 < n && a[j + 1] - a[i] <= d) j ++;
        ans += ll((ll)(j - i) * (ll)(j - i - 1) / 2) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}


全部评论

相关推荐

07-24 19:01
门头沟学院 Java
后天笔试,又要开始做题了
Sairus:明天10:00笔试
投递京东等公司10个岗位
点赞 评论 收藏
分享
程序员小白条:主要没亮点,项目也是网上的,平平无奇,那只能海投了,奖项总得有一些,然后就是现在最好是前后端都会,自己能做项目并且运维的,要么找星球项目改改,要么找个开源项目改改,自己能拓展功能才是主要的,跟做效率很低很低
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务