余杭区奋进杯:T7-赛后AC

问题讨论区 提高段
1 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n), b(n);

    // 读入数组 a
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    // 读入数组 b
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }

    // 计算旋转45度后的坐标
    vector<int> p(n), q(n);
    for (int i = 0; i < n; i++)
    {
        p[i] = a[i] + b[i];
        q[i] = a[i] - b[i];
    }

    // 排序以便快速计算
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());

    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        // 计算每个点对所有其他点的贡献
        ans += 1LL * (2 * i - n + 1) * p[i];
        ans += 1LL * (2 * i - n + 1) * q[i];
    }

    cout << ans << endl;
    return 0;
}
以上内容由AI生成,仅供参考
  • 写题写到怀疑人生，题目喂给AI还改了12次
  • 数学原理，本人就是"我是烟鬼，这就是肺雾"
  • 最终优化到O(n·log n),只能说能过
1 个赞