首页 > 试题广场 >

谐距下标对

[编程题]谐距下标对

热度指数：9227 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $\{a_1,a_2,\dots,a_n\}$ 。若下标满足 $i<j$ 且 $a_j-a_i = j-i$ ，则称 $(i,j)$ 为一对谐距下标对。

$\hspace{15pt}$ 请计算数组中的谐距下标对数量。

输入描述:

第一行输入整数 。
第二行输入  个整数 。

输出描述:

输出一个整数，表示谐距下标对数量。

示例1

输入

6
1 2 3 4 5 6

输出

算法知识视频讲解

上凡不思仙

原式可推导为 a_i- i = a_j- j

核心思路是在每次读取后将 a_i- i作为元素存储为数组，然后通过排序或者其他方式获得有多少组相同的值，然后对每组相同的值组合后求和。

_{注意存储元素的数组需要预先分配内存。}

_{#include <stdio.h>
#include <stdlib.h>

int FiQsort(const void* PvA, const void* PvB) {
    long long ViA = *(const long long*)PvA;
    long long ViB = *(const long long*)PvB;
    if (ViA < ViB) return -1;
    else if (ViA == ViB) return 1;
    else return 0;
}

int main() {
    long long ViNu = 0;
    long long ViNt = 0;
    long long ViN;

    scanf("%lld", &ViN);

    long long* AiN = malloc(sizeof(long long) * ViN);
    long long* AiNL = malloc(sizeof(long long) * ViN);

    for (long long ViLoop = 0; ViLoop < ViN; ViLoop++) {
        scanf("%lld", &AiN[ViLoop]);
        AiNL[ViLoop] = AiN[ViLoop] - ViLoop;
    }

    qsort(AiNL, ViN, sizeof(long long), FiQsort);

    for (long long ViLoop = 0; ViLoop < ViN; ViLoop++) {
        if (AiNL[ViLoop] == AiNL[ViLoop + 1]) {
            ViNt++;
            continue;
        } else if (ViNt > 0) {
            ViNu = ViNu + (ViNt * (ViNt + 1)) / 2;
        }
        ViNt = 0;
    }

    printf("%lld", ViNu);

    free(AiN);
    free(AiNL);
    
    return 0;
}}

发表于 2026-03-03 11:39:56 回复(0)