首页

本来使用 ppt 汇报的，这里转成图片了～

主要介绍原理和讲解 POJ1990~

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
    int index; //x 坐标
    int vol;   // 音量
} cow[20002];
long long C1[20002]; // 位置在 i 左侧的牛的数量
long long C2[20002]; // 位置在 i 左侧的牛的坐标的和
long long N;         // 牛的数量
// 按音量从小到大排序
bool compare(node a, node b)
{
    return a.vol < b.vol;
}
// 获取最低位 1
long long getlowest_1_bit(long long x)
{
    return x & (-x); // 原码和反码加 1 (即负数) 的 & amp; 就是最低位的 1
}
// 用 value 更新结点 x 的值
void update(int x, int value, long long C[])
{
    for (int i = x; i <= 20000; i += getlowest_1_bit(i)) // 每次更新 i 直到越界
    {
        C[i] += value; // 只需按照顺序向上更新
    }
}
// 查询高于结点 x 的值之和
long long inquiry(int x, long long C[])
{
    long long sum = 0;
    for (int i = x; i > 0; i -= getlowest_1_bit(i)) // 每次更新 i 直到越界
    {
        sum += C[i]; // 路径上的值相加
    }
    return sum;
}
int main()
{
    scanf("%d", &N);
    long long sum_leftindex;     //i 左侧的坐标和
    long long sum_leftcow;       //i 左侧的牛数量
    long long ans = 0;           // 记录答案
    long long sum = 0;           // 记录总的坐标和
    for (int i = 1; i <= N; i++) // 读入 N 头牛的数据
    {
        scanf("%d %d", &cow[i].vol, &cow[i].index);
    }
    sort(cow + 1, cow + 1 + N, compare); // 音量排序
    for (int i = 1; i <= N; i++)
    {
        sum_leftcow = inquiry(cow[i].index, C1);
        sum_leftindex = inquiry(cow[i].index, C2);
        //i 左边的牛的音量等于牛 i 的坐标 * 牛 i 左侧牛的数量 - 牛 i 左侧牛的坐标和
        ans += cow[i].vol * (sum_leftcow * cow[i].index - sum_leftindex);
        //i 右边的牛的音量等于牛 i 右侧牛的坐标和 - 牛 i 的坐标 * 牛 i 右侧牛的数量
        ans += cow[i].vol * (sum - sum_leftindex - cow[i].index * (i - sum_leftcow - 1));
        update(cow[i].index, 1, C1);            // C1 加入这头牛
        update(cow[i].index, cow[i].index, C2); // C2 加入该牛的坐标
        sum += cow[i].index;
    }
    printf("%lld", ans);
    return 0;
}

  


   


    

  
    
      
    
    更新于