小编SHB*_*SHB的帖子

我正在使用这个比较函数来排序一个由long long int组成的数组.

int compare(const void * p1,const void * p2)
{
    return (* (long long int * )a-*(long long int * )b);
}
qsort(array,no of elements,sizeof(long long int),compare)

这适用于小的nos但是当数组包含10 ^ 10的nos时它会得到错误的结果吗？

我犯的错是什么？

假设我有一个长度为L的数组A.我将给出n个区间(i,j)并且我必须递增A [i]和A [j]之间的所有值.哪个数据结构最适合给定的操作？
间隔是事先已知的.

问题如下:

Lazer Tag由一个小组游戏组成,在整个游戏中你被分配了固定数量的子弹(通常称为激光射击).每个右手射击你的目标敌人,给你一分.

考虑一系列的命中和未命中,它们可以用"x"和"o"的形式表示,其中"o"表示命中,"x"表示未命中.假设该系列的形式为"xxxoooxxxxooxxo",则您的最终得分将等于即将3^2 + 2^2 +1^2整个游戏中每个最大连续命中数的平方加起来.

正确击中第j次击球的概率(1≤j≤n)是P(j).简单来说,在第j个转弯处获得系列中"o"的概率是P(j).您需要在回合结束时计算预期得分.

我可以使用memoization理解这个O(n ^ 2)解决方案,但问题需要O(n)解决方案.我见过O(n)解决方案,但我无法理解.O(n)解决方案如下:

for(i = 1; i <= n; i++)
    dp[i] = (dp[i-1] + p[i-1]) * p[i];   
for(i = 1; i <= n; i++)
    ans+=2 * dp[i] + p[i];

其中p [i]是击中第i个目标的概率.谁能解释O(n)解决方案是如何工作的？