题目链接
简单说一下题意,就是说给了一个数组,每个区间长度都有一个权值.定义了一个f函数即 i->j区间的区间和×该区间长度的权值 然后给了两个求和符号.不好描述.具体看题目吧.
这种表达式啥的都给了的就只需要考虑怎么算的快一点就好了.不用怎么转弯.
写完后看了下网上的题解,感觉和我的思路不太一样,这里提供一下我的思路.
最暴力的版本,两个for循环.就不提了.
但模拟一下暴力版本还是需要的.怎么算呢?
假设n = 5.计算过程(暴力版本是从左往右算):
1-1 2-2 3-3 4-4 5-5
1-2 2-3 3-4 4-5
1-3 2-4 3-5
1-4 2-5
1-5
从上往下观察这个式子可以发现一个问题,如果我们按照区间长度来算的话.可能会是一个更好的选择,不过这么算有一个问题.区间有些重复了.比如说看第二行.
1 2 2 3 3 4 4 5 这行里面除了1-5大区间之外,又算了一遍2-4这个区间
第三行 1 2 3 2 3 4 3 4 5 这行除了1-5算了一遍 2-4算了两遍 3-3算了三遍
第四行分析后也 2-4这个区间算了两遍
有没有发现什么规律?我们假设一开始设置两个指针p1和p2,让p1指向开头,p2指向结尾 这是第一次计算时的有效区间,我们算完之后让p1++,p2–.然后用一个变量tmp存下这个值.然后发现越过中点之后.虽然还是加法但其实是把那段区间给减掉了.我表达的可能不是很好,可以自己画一画,想一想.就会发现这道题其实很简单.不过有一个坑点就是取模运算要注意一下了(因为这个WA了5发差点怀疑人生).减法取模的话要记得+mod值再取模.
附上代码