推荐:(15条消息) 前缀和_wsir的博客-CSDN博客_前缀和是什么意思
练习：【算法2-1】前缀和与差分 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
一维前缀和
解释：将要求的所有结果加起来，然后利用b[i]-b[i-1]将本来想的到的数组重新复现
一维递推式：b[i]=b[i-1]+a[i]//结束后得到的b[i]是总和（依靠递推式），a[i]是每次输入的元素
//不使用数组方式输入也没有问题
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdbool>
#include <string.h>
#include <math.h>
using namespace std;
int main()
{
int a[100005] = {0};
int b[100005] = {0};
int n;
cin >> n;
for (int i=1;i<=n;i++)
{
cin >> a[i];
b[i] = b[i-1] + a[i];
}
int t;
cin >> t;
while (t--)
{
int l,r;
int sum = 0;
cin >> l >> r;
sum = b[r] - b[l-1];
printf("%d\n",sum);
}
return 0;
}
一道前缀和+二分
题目：Problem - 978C - Codeforces
详细：
C. Letters
///////////////
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
/////////////////////////
There are nn dormitories in Berland State University, they are numbered with integers from 11 to nn. Each dormitory consists of rooms, there are aiai rooms in ii-th dormitory. The rooms in ii-th dormitory are numbered from 11 to aiai.
A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all nn dormitories is written on an envelope. In this case, assume that all the rooms are numbered from 11 to a1+a2+⋯+ana1+a2+⋯+an and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.
For example, in case n=2n=2, a1=3a1=3 and a2=5a2=5 an envelope can have any integer from 11 to 88 written on it. If the number 77 is written on an envelope, it means that the letter should be delivered to the room number 44 of the second dormitory.
For each of mm letters by the room number among all nn dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.
Input
The first line contains two integers nn and mm (1≤n,m≤2⋅105)(1≤n,m≤2⋅105) — the number of dormitories and the number of letters.
The second line contains a sequence a1,a2,…,ana1,a2,…,an (1≤ai≤1010)(1≤ai≤1010), where aiai equals to the number of rooms in the ii-th dormitory. The third line contains a sequence b1,b2,…,bmb1,b2,…,bm (1≤bj≤a1+a2+⋯+an)(1≤bj≤a1+a2+⋯+an), where bjbj equals to the room number (among all rooms of all dormitories) for the jj-th letter. All bjbj are given in increasing order.
Output
Print mm lines. For each letter print two integers ff and kk — the dormitory number ff (1≤f≤n)(1≤f≤n) and the room number kk in this dormitory (1≤k≤af)(1≤k≤af) to deliver the letter.
Examples
input
Copy
3 6
10 15 12
1 9 12 23 26 37
output
Copy
1 1
1 9
2 2
2 13
3 1
3 12
input
Copy
2 3
5 10000000000
5 6 9999999999
output
Copy
1 5
2 1
2 9999999994
Note
In the first example letters should be delivered in the following order:
- the first letter in room 11 of the first dormitory
- the second letter in room 99 of the first dormitory
- the third letter in room 22 of the second dormitory
- the fourth letter in room 1313 of the second dormitory
- the fifth letter in room 11 of the third dormitory
- the sixth letter in room 1212 of the third dormitory
题解（理解二分与前缀和）：
#include<bits/stdc++.h>
using namespace std;
long long a[20010]={0},b[20010]={0},c;
int main()
{
long long n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+a[i];//前缀和部分
}
while(m--)
{
cin>>c;//input
int l=1,r=n;
while(l<r)//二分部分
{
int mid=l+r>>1;
if(b[mid]<c) l=mid+1;
else r=mid;
}
cout<<r<<" "<<c-b[r-1]<<endl;//output
}
return 0;
}
Comments NOTHING