小编kin*_*gW3的帖子

我给出了一个数组和LR类型的查询列表,这意味着找到任意两个数组元素之间的最小绝对差值,使得它们的索引在L和R之间(包括这里)数组的起始索引是1而不是0 )

例如,使用元素2 1 8 5 11获取数组a,然后查询1-3将是(2 1 8)答案将是1 = 2-1,或查询2-4(1 8 5)其中答案是3 = 8-5

现在这很容易,如果你必须查看一个间隔,你对间隔进行排序,然后比较第i个元素和第i + 1个,并存储每个i的最小差异.

问题是我会有很多间隔来检查我必须保持原始数组完好无损.

我所做的是我构造了一个新的数组b,其索引来自第一个,使得a [b [i]] <= a [b [j]],i <= j.现在对于每个查询,我循环遍历整个数组,并查看b [j]是否在L和R之间,如果它将其绝对差值与第一个下一个元素进行比较,也是在L和R之间保持最小值,然后执行相同操作那个元素直到你走到尽头.

这是低效的,因为对于每个查询,我必须检查数组的所有元素,特别是如果查询与数组的大小相比较小.我正在寻找一种节省时间的方法.

编辑:数字不必是连续的,也许我给出了一个糟糕的数组作为一个例子,我的意思是例如,如果它是1 5 2那么最小的差异是1 = 2-1.在排序数组中,最小的差异保证在两个连续元素之间,这就是我考虑排序的原因

在这几年泡泡杯(完成)有问题NEO(我无法解决),这要求

给定具有n个整数元素的数组.我们将它分成几个部分(可能是1),每个部分是连续的元素.在这种情况下的NEO值通过以下公式计算:每个零件的值的总和.零件的值是该零件中所有元素的长度乘以其长度.

示例:我们有数组:[2 3 -2 1].如果我们把它除以:[2 3] [-2 1].然后NEO =(2 + 3)*2 +( - 2 + 1)*2 = 10 - 2 = 8.

数组中元素的数量小于10^5,数字是-10^6和之间的整数10^6

我已经尝试过像分而治之的东西,如果它增加最大NEO数,则不断地将数组分成两部分,否则返回整个数组的NEO.但遗憾的是该算法具有最差的O(N ^ 2)复杂度(我的实现如下)所以我想知道是否有更好的解决方案

编辑:我的算法(贪婪)不起作用,例如[1,2,-6,2,1]我的算法返回整个数组,而获得最大的NEO值是取部分[1,2],[-6],[2,1],给出NEO值(1+2)*2+(-6)+(1+2)*2=6

#include <iostream>
int maxInterval(long long int suma[],int first,int N)
{
    long long int max = -1000000000000000000LL; 
    long long int curr;
    if(first==N) return 0;
    int k;
    for(int i=first;i<N;i++)
    {
        if(first>0) curr = (suma[i]-suma[first-1])*(i-first+1)+(suma[N-1]-suma[i])*(N-1-i); // Split the array into elements …

所以,我试图创建一个简单的程序来计算国防部第n个Fibonacci数10^9+7使用倍增公式与F[0]=0和F[1]=1.程序似乎可以在我的计算机上使用编译器VS2010和CodeBlocks与MinGW一起工作但是在ideone上测试我的程序会为每个输入返回0.似乎在第一次迭代之后,F.find(n)实际上找到了不应该存在的元素.这是我的代码(在VS2010中,我刚刚更改了包含).

#include <bits/stdc++.h>

using namespace std;
std::map<unsigned long long,unsigned long long> F;
unsigned long long fib(unsigned long long n)
{
    if(n==-1) return 0; // Shifting index by 1
    if(n==0) return 1;
    if(n==1) return 1;
    if(F.find(n) != F.end()) return F[n]; // This seems to be the problem,
    else
    {
        if(n%2==0) //
        {
            F[n/2-1] = fib(n/2-1)%1000000007;
            F[n/2] = fib(n/2)%1000000007;
            return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;
        }
        else
        {
            F[n/2] = fib(n/2)%1000000007;
            F[n/2+1] = fib(n/2+1)%1000000007;
            return F[n] …

我的 gcc:线程模型: posix

gcc 版本 8.1.0（x86_64-posix-seh-rev0，由 MinGW-W64 项目构建）

我正在尝试创建一个简单的应用程序，它使用 gcc 和 intel 语法对两个文件 saberi.c 和 saberi.s 的两个数字求和，其中 saberi 表示求和。

萨伯里.c

#include <stdio.h>
int saberi(int a, int b);
int main()
{   
    int a, b;
    scanf("%d %d", &a, &b);
    printf("Sum is: %d\n", saberi(a, b));
    return 0;
}

军刀

.intel_syntax noprefix
.text
    .globl saberi
saberi:
    enter 0,0
    mov eax, edi
    add eax, esi
    leave
    ret

然后我执行 gcc saberi.c saberi.s ，当我打开可执行文件并输入任意两个数字（例如 1 和 2）时，我会得到一个随机值作为总和。