题解 P5094 【[USACO2004OPEN]MooFest 狂欢节】

06ray · 2018-12-16 18:43:50 · 题解

难度:普及-

直接n方暴力就能水过。

先按奶牛的听力值从小到大排序，然后在暴力枚举每个奶牛排序后之前的奶牛，累加它们坐标的绝对值之差乘这个奶牛的听力值，就是最终的答案。

话不多说，上代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct node{
    int x,y;
}a[50100];//用结构体存入每个奶牛的坐标和听力值，方便排序
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);//以奶牛的听力值从小到大排序
    long long ans=0;
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<i; j++)
        {
            ans+=a[i].x*abs(a[i].y-a[j].y);//累加
        }
    }
    cout<<ans;
    return 0;
}

话说是谁把它评到黑色的