作者qazkevin (Linus)
看板C_and_CPP
标题[问题] HackerRank - 阵列的相关问题
时间Fri Jan 5 21:09:21 2018
题目: 输入N与M，N表示阵列个数，M表示操作次数。阵列初始值为0。
操作内容为输入a, b, k。a代表第a个元素，b代表第b个元素。
将a至b的元素(包含a, b两个位置的元素)加上整数k。
最後找出阵列元素中最大值。
Sample Input:
5 3
1 2 100
2 5 100
3 4 100
表示N=5, M=3，
所以代表阵列元素有五个，操作次数为三，所以有以下三行操作
第一次操作: a=1, b=2, k=100
第二次操作: a=2, b=5, k=100
第三次操作: a=3, b=4, k=100
Sample Output:
200
Explanation:
第一次操作: 100 100 0 0 0.
第二次操作: 100 200 100 100 100.
第三次操作: 100 200 200 200 100.
所以最大值为 200.
Solution:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long int N,K,p,q,sum,i,j,max=0,x=0;
cin>>N>>K;
long int *a=new long int[N+1]();
for(i=0;i<K;i++)
{
cin>>p>>q>>sum;
a[p]+=sum;
if((q+1)<=N) a[q+1]-=sum;
}
for(i=1;i<=N;i++)
{
x=x+a[i];
if(max<x) max=x;
}
cout<<max;
return 0;
}
小弟资质愚钝，一直不懂这个解答的逻辑与演算法，
坦白说思考了两天，还是看不太懂QQ
请问有哪位大大懂程式码的想法是什麽吗?
感激不尽!!!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.166.24.39
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1515157763.A.C4A.html
1F：→ Sylveon: 考虑数列与前缀和的关系 01/05 21:17
2F：→ Sylveon: 演算法笔记 Sequence2 最後面 01/05 21:21
3F：→ qazkevin: Sylveon大大，请问有网址吗? 01/05 22:42
4F：→ qazkevin: 请问一下所以第一个for回圈代表的是把三个序列做微分? 01/05 23:00
5F：推 fishinair: 我只是直觉的想到，从第几个到第几个加多少而已.. 01/05 23:09
6F：→ qazkevin: fishinair大大，我一开始也是这样写的...哈哈 01/05 23:17
7F：→ Sylveon: 我在某个比赛出过一样的题目xd，你可以考虑只有一个操作 01/06 03:56
8F：→ Sylveon: 时，把原来数列ai加上k，然後做前缀和(第二个for)的话， 01/06 03:57
9F：→ Sylveon: 效果就是Si以後的所有项都加上k，因此再用-k吧不要加的 01/06 03:57
10F：→ Sylveon: 部分抵销 01/06 03:57
11F：推 jobsdone: 我是想像成unit step function的叠合,感觉比较视觉化 01/06 07:44
12F：→ jobsdone: 把题目想像成产生方波,然後方波的叠合这样子 01/06 07:49
13F：→ qazkevin: 感谢各位大大的回答，小弟好像对这解法有fu了~ 01/06 22:57