首页 > 其他分享 >前缀和

前缀和

时间:2024-08-13 16:29:24浏览次数:11  
标签:std 前缀 int namespace long define

1 前缀和练习

1)跳楼机人数安排

题目

点击查看代码
中文解释#include <bits/stdc++.h>

using namespace std;

#define int long long

#define dbg(x) cout << #x << '=' << x << endl

const int N = 2e5 + 15;

int n, m, q[N], a[N];

signed main()
{
ios::sync_with_stdio (false); cin.tie (nullptr);

cin >> n >> m;

for (int i = 1; i <= n; i++) cin >> q[i];
for (int i = 1; i <= n; i++) cin >> a[i];

for (int i = 1; i <= n; i++) q[i] = q[i - 1] + q[i];

int sum = 0;
for (int i = 1; i <= n; i++)
{
sum += a[i];
int u = lower_bound (q + 1, q + 1 + n, sum) - q;//这里是-q.第一个大于等于

if (q[u] == sum) u++;//u仓非空

if (u <= n) cout << n - u + 1 << '\n';
else 
{
    cout << n << '\n';
    sum = 0;
} 
}

return 0;
}  

标签:std,前缀,int,namespace,long,define
From: https://www.cnblogs.com/hoshino-/p/18357212

相关文章

  • 长度最小的子数组 | LeetCode-209 | 双指针+滑动窗口 | 前缀和+二分查找 | Java详细注
    ......
  • 二维前缀和学习指南
    为什么我为OI泪目,因为我菜得离谱......二维前缀和引子二维前缀和,仅仅是由一维前缀和进阶了一维而已。为了方便后面的学习,我先给出二维前缀和重点代码。处理二维前缀和for(inti=1;i<=n;i++) for(intj=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[......
  • Java | 图片地址查询返回参数自动拼接图片前缀地址
    代码介绍自定义的JsonSerializer来处理图片URL的拼接,增加了灵活性和可配置性。关键点:自动拼接域名:通过properties.getEndpoint()从配置文件中获取Minio接口域名,然后根据条件决定是否拼接域名。处理多个图片URL:代码处理了可能包含多个图片URL的情况(以逗号分隔),并且确保了每个UR......
  • 第四章 前缀和,差分
    目录1前缀和1.1什么是前缀和?1.2前缀和的作用注意事项:1.3一维前缀和1.3.1代码模板1.3.2例题分析:  代码:1.4二维前缀和 1.4.1代码模板2差分2.1什么是差分?2.2差分的作用注意事项: 2.3一维差分2.3.1代码模板 2.4二维差分2.4.1代码模板3前缀......
  • 前缀和 & 差分
    1.前缀和前缀和是一种支持不带修改,多次查询的数据结构。1.1一维前缀和维护前缀和数组\(b_i=\sum\limits_{j=1}^ia_i\),则\(b\)数组还可以通过递推式\(b_i=b_{i-1}+a_i\)得到。当需要求区间\([l,r]\)的和,就可以通过\(b\)数组\(b_r-b_{l-1}\)得到,时间复杂度\(\mat......
  • 洛谷题单指南-前缀和差分与离散化-P1904 天际线
    原题链接:https://www.luogu.com.cn/problem/P1904题意解读:给出(左端点,高度,右端点)表示的若干建筑,要输出其轮廓,所谓轮廓就是每个点被覆盖的最高建筑的高度所描绘的线。解题思路:如果能计算每个点被覆盖的最高建筑的高度,用数组h[10005]保存,那么输出轮廓的过程只需要枚举每一个点,如......
  • 「Day 2—贪心问题&分治&前缀和」
    贪心问题定义顾名思义,越贪越好。。。习题P1094[NOIP2007普及组]纪念品分组思路简单来说:最少的+最多的,利用双指针。代码#include<algorithm>#include<iostream>usingnamespacestd;intw,n;intp[30005];intmain(){cin>>w;cin>>n;for(inti=1;i......
  • 算法【构建前缀信息解决子数组问题】
    本文需要对掌握哈希表的用法。构建某个前缀信息比如最早出现、最晚出现、出现次数等,是很常见的技巧。除此之外,还有很多种类的前缀信息可以构建出来,解决很多子数组相关问题。下面通过几个题目加深对构建前缀信息这个方法的理解。题目一简要描述:构建前缀和数组。快速解决子......
  • 算法【前缀树】
    注意:学习本篇最少应知道什么是树结构和哈希表怎么用。前缀树又叫字典树,英文名trie。每个样本都从头节点开始根据前缀字符或者前缀数字建出来的一棵大树,就是前缀树。没有路就新建节点;已经有路了,就复用节点。前缀树的使用场景:需要根据前缀信息来查询的场景前缀树的优点:根......
  • DAY4 前缀和与差分
    本文中将要介绍前缀和与差分的简单知识,全部题目来自acwing,是对y总讲解的简单归纳。题目:acwing795输入一个长度为 n的整数序列。接下来再输入 m 个询问,每个询问输入一对 l,r。对于每个询问,输出原序列中从第 l个数到第 r个数的和。输入格式第一行包含两个整数 n和 ......