POJ 1990 MooFest(树状数组)_AC_way的博客-程序员宅基地

技术标签: ACM—树状数组  algorithm  

MooFest
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 5395   Accepted: 2329

Description

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing. 

Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)). 

Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume. 

Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows. 

Input

* Line 1: A single integer, N 

* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location. 

Output

* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.  

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

57


先按听力值从小到大排个序,保证当前的牛与前面的联系时,取当前牛的听力值,再用两个树状数组,一个记录所有所有坐标点的位置个数,这样就可以查询大于当前坐标的个数和小于当前坐标的个数,另一个记录所有坐标点的和,这样就可以查询小于和大于当前坐标的所有坐标的和,最后用当前听力值*(大于当前坐标的坐标和—大于当前坐标的个数*当前坐标+小于于当前坐标的个数*当前坐标—小于当前坐标的坐标和)。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=20000+1000;
struct node
{
    int x;
    int y;
}a[maxn];
long long b[maxn];
int c[maxn];
bool cmp(node p,node q)
{
    return p.x<q.x;
}
int low(int k)
{
    return (k&(-k));
}
void update(int k,int v)
{
    while(k<maxn)
    {
        b[k]+=v;
        k+=low(k);
    }
}
void update2(int k,int v)
{
    while(k<maxn)
    {
        c[k]+=v;
        k+=low(k);
    }
}
long long getsum(int k)
{
    long long ans=0;
    while(k>0)
    {
        ans+=b[k];
        k-=low(k);
    }
    return ans;
}
int getsum2(int k)
{
    int ans=0;
    while(k>0)
    {
       ans+=c[k];
       k-=low(k);
    }
    return ans;
}
int main()
{
    long long ans;
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        ans=0;
        sort(a,a+n,cmp);
        long long temp=0;
        for(int i=0;i<n;i++)
        {
            long long x1=getsum(a[i].y);//小于当前坐标的坐标和
            long long y1=temp-x1;//大于当前坐标的坐标和
            int x2=getsum2(a[i].y);//小于当前坐标的个数
            int y2=i-x2;//大于当前坐标的个数
            ans+=(long long)a[i].x*(y1-a[i].y*y2);
            ans+=(long long)a[i].x*(a[i].y*x2-x1);
            update(a[i].y,a[i].y);
            update2(a[i].y,1);
            temp+=a[i].y;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/caduca/article/details/40107637

智能推荐

初学Python的感受_kaiixin的博客-程序员宅基地

一.Python的来历——Python的创始人为吉多*范罗苏姆(Gudio van Rossum)1.1989年的圣诞节期间,吉多*范罗苏姆为了在阿姆斯特丹打发时间,决心开发一个新的解释程序,作为ABC语言的一种继承。2.ABC是由吉多参加设计的一种教学语言,就吉多本人看来,ABC这种语言非常优美和强大,是专门为非专业程序员设计的。但是ABC语言并没有成功,究其原因,吉多认为是非开发造成的。...

教你如何自定义实现可上下滑动的ViewPager_康小白Code的博客-程序员宅基地_viewpager上下滑动

前言:要问最近什么App最火?那必须是抖音啊!火的不要不要的!抖音的界面在App中算是独树一帜,一进去就是全屏的视频播放界面,上下滑可以切换视频,左滑进入故事相机界面,右滑进入个人中心。这样的效果在Android中应该如何实现呢? 我想到了ViewPager,但是ViewPager只支持左右滑动,上下滑动该怎么实现?我可以不可以把它翻转一下呢?答案是肯定的!OK,我们进入正文。githu

Silverlight/Windows8/WPF/WP7/HTML5周学习导读(10月29日-11月4日)_jv9的博客-程序员宅基地

Silverlight/Windows8/WPF/WP7/HTML5周学习导读(10月29日-11月4日)本周Silverlight学习资源更新ArcGIS 10.1 for Server 服务端查询统计 -ArcGIS API for Silverlight 实arcgisserver_bookSilverlight文件上传kuki89Silverlight访问Wcf Ria Library的问

软件测试金字塔 —— Mike Cohn_白码会说的博客-程序员宅基地

Time will tell.在敏捷方法中,持续集成是其基石,持续集成的核心是自动化测试。关于测试金字塔,来自Martin Fowler。测试金字塔的概念来自Mike Cohn,在他的书《Succeeding With Agile》中详细描述着:“测试金字塔最底层是单元测试,然后是业务逻辑测试,最后是端到端的测试(GUI或CLI)。”在职业生涯中,多次听到过自动化测试,自动化测试意味着端到端的通过界面完成的测试。完成这种自动化测试的工具一般是录制然后回放,初始使用很容易,不需要任何编码技能。.

分享Silverlight/Windows8/WPF/WP7/HTML5周学习导读(6月18日-6月24日)_jv9的博客-程序员宅基地

分享Silverlight/Windows8/WPF/WP7/HTML5周学习导读(6月18日-6月24日)本周Silverlight学习资源更新Silverlight读取与设置Cookies任天龙jayceSilverlight 后台CS实现动态创建dataGrid并为数据多的列实现自动分行或换行xuan444150Silverligh

腾讯云Centos7搭建图形界面详解_「已注销」的博客-程序员宅基地

对于腾讯云中无界面的centos7系统进行界面环境的搭建。

随便推点

6、springMvc访问静态资源_soldierluo的博客-程序员宅基地

 1          首先看为什么访问不到静态文件,如下是web.xml文件的配置,它配置了springMvc作为servlet的处理程序,其中&amp;lt;url-pattern&amp;gt;/&amp;lt;/url-pattern&amp;gt;表示将所有请求交给springmvc处理,而springmvc的请求都是通过RequestMapping进行映射的,很显然静态资源并没有使用RequestMapping来映射...

MCS-51单片机的存储器组织结构_justarone的博客-程序员宅基地

MCS-51单片机的存储器组织结构  Author: Aaron Wong  and http://blog.csdn.net/yhmhappy2006/article/details/1495173特点:哈佛结构,程序存储器与数据存储器分开,两者各有一个相互独立的64K(0x0000 ~ 0xFFFF)的寻址空间(准

解决fonts/fontawesome-webfont.woff2 404 (Not Found) fonts/fontawesome-webfont.ttf 404 (Not Found)_k_e_vi_n的博客-程序员宅基地_无法加载源映射: 无法解析font-awesome/fonts/fontawesome-webfon

只是记录思路1、确认springMVC能正确访问静态资源,三种方法:1)在web.xml中配置servelet-mapping default 2)在spring-mvc.xml中配置&amp;lt;mvc:default-servlet-handler/&amp;gt;  3)在spring-mvc中配置&amp;lt;mvc:resources mapping=&quot;/js/**&quot; location=&quot;/js/&quot;/&amp;...

Makefile知识点-3------makefile定义“空格”变量的定义方法_helmsgao的博客-程序员宅基地_makefile定义空变量

下面再介绍两个定义变量时我们需要知道的,请先看一个例子,如果我们要定义一个变量,其值是一个空格,那么我们可以这样来:nullstring :=space := $(nullstring) # end of the linenullstring 是一个Empty变量,其中什么也没有,而我们的space的值是一个空格。因为在操作符的右边是很难描述一个空格的,这里采用的技术很管用,先

Jetty安装 - ITBOOK - itbook.com_itbook.com的博客-程序员宅基地

原创来源:IT书 - itbook.com1下载jettywget https://repo1.maven.org/maven2/org/eclipse/jetty/jetty-distribution/9.4.26.v20200117/jetty-distribution-9.4.26.v20200117.tar.gztar -zxvf jetty-distribution-9.4.26....

ZooKeeper介绍___HelloWorld__的博客-程序员宅基地

我本人曾经使用过 ZooKeeper 作为 Dubbo 的注册中心,另外在搭建 Solr 集群的时候,我使用到了 ZooKeeper 作为 Solr 集群的管理工具。前几天,总结项目经验的时候,我突然问自己 ZooKeeper 到底是个什么东西?想了半天,脑海中只是简单的能浮现出几句话:Zookeeper 可以被用作注册中心。Zookeeper 是 Hadoop 生态系统的一员。构建...

推荐文章

热门文章

相关标签