c782: PC. 孤單值量測

2019-08-25

內容

在一條馬路上有 n 個人，每個人都站在一個位置 a_i，都有一個孤單評測值 w_i。現在里長想計算這些人的孤單值總和，如果第 i 個人和第 j 個人的位置相差大於 k 公尺，那麼他們會對總孤單值 S 貢獻 w_i*w_j。現在，請你幫我求出 S。

輸入

輸入第一行有一個正整數 t(t≤5)，表示一共有 t 筆測資。
每筆測資的第一行有兩個正整數 n(n≤2000000),k(k≤1000000000)，第二行有 n 個整數 a_i(0≤ai≤1000000000,1≤i≤n)，輸入保證從小到大。
第三行有 n 個整數 w_i(−1000≤w_i≤1000,1≤i≤n)。

1
5 3
1 2 3 4 5
2 3 4 5 6

輸出

對每一筆測資，請輸出一個正整數 S。

12

解題思路

依據題意"輸入保證從小到大"所以當 i < j 時 a[i] 必小於 a[j]，因此可以假設當第 i 項可以與第 j 項產生孤單值時，第 1~i 項都可以和第 j 項產生孤獨值，因為比 i 小的值與 j 的距離必定比 i 更遠。

所以先找到距離 j 點最近但距離又大於 k 的 i 點，並將所有 i 點紀錄至陣列 v[]，如此一來之後要算孤獨單值時就不用再從 0 開始遍歷，直接查表 v[] 就好。

接下來計算孤獨值，因為孤獨值是互相的，所以只算往前的孤獨值避免重複計算。
假如 j = 5、 i = 3，且 j 和 i 可以產生孤獨值，那點 j 的的孤獨值就是

w[1] * w[5] + w[2] * w[5] + w[3] * w[5]

而根據乘法的分配律，可以將上式轉為

(w[1] + w[2] + w[3]) * w[5]

這樣在算孤獨值時只要先將答案加上 w[v[i]] * w[i]，再把 w[i]加上 w[i-1]，就可以省下迴圈做連續乘法的時間了。

本題輸入測資非常大，輸入優化可以壓掉不少時間。

完整程式碼

正常版

AC (0.3s, 23MB)

#include <stdio.h>
#define MAX 2000010

long long sum, w[MAX];
int kase, n, k;
int a[MAX], v[MAX];

int main()
{
    scanf(" %d", &kase);
    while (kase--)
    {
        sum = 0;
        scanf(" %d %d", &n, &k);
        for (int i = 1; i <= n; i++)
            scanf(" %d", &a[i]);
        for (int i = 1, s = 1; i <= n; i++)
        {
            while (a[i] - a[s] > k)
                s++;
            v[i] = s - 1;
        }
        for (int i = 1; i <= n; i++)
        {
            scanf(" %d", &w[i]);
            sum += w[v[i]] * w[i];
            w[i] += w[i - 1];
        }
        printf("%lld\n", sum);
    }
    return 0;
}

輸入優化版

AC (41ms, 24MB)

#pragma GCC optimize(3)
#include <stdio.h>
#define MAX 2000010
#define BUFMAX 1048576

long long sum, w[MAX];
int kase, n, k, length = BUFMAX, a[MAX], v[MAX];
char buf[BUFMAX], tmp, * pt = buf, * end = buf;

inline char freadChar()
{
    if (pt == end)
    {
        if (length < BUFMAX)
            return EOF;
        length = fread(buf, 1, BUFMAX, stdin);
        end = buf + length;
        pt = buf;
    }
    return *pt++;
}

inline void freadUInt(int* val)
{
    while ((tmp = freadChar()) < '0')
        if (tmp == EOF) return;
    *val = tmp - '0';
    while ((tmp = freadChar()) >= '0')
        * val = (*val << 3) + (*val << 1) + (tmp - '0');
}

inline void freadLongLong(long long* val)
{
    while ((tmp = freadChar()) < '-')
        if (tmp == EOF) return;
    if (tmp == '-')
    {
        *val = freadChar() - '0';
        while ((tmp = freadChar()) >= '0')
            * val = (*val << 3) + (*val << 1) + (tmp - '0');
        *val = -*val;
    }
    else
    {
        *val = tmp - '0';
        while ((tmp = freadChar()) >= '0')
            * val = (*val << 3) + (*val << 1) + (tmp - '0');
    }
}

int main()
{
    scanf(" %d", &kase);
    while (kase--)
    {
        sum = 0;
        freadUInt(&n), freadUInt(&k);
        for (int i = 1; i <= n; i++)
            freadUInt(&a[i]);
        for (int i = 1, s = 1; i <= n; i++)
        {
            while (a[i] - a[s] > k)
                s++;
            v[i] = s - 1;
        }
        for (int i = 1; i <= n; i++)
        {
            freadLongLong(&w[i]);
            sum += w[v[i]] * w[i];
            w[i] += w[i - 1];
        }
        printf("%lld\n", sum);
    }
    return 0;
}