题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3015

题目大意:

有一些树,这些树的高度和位置给出。现在高度和位置都按从小到大排序,对应一个新的rank,任意两棵树的值为min(高度的rank) * abs(位置差的绝对值)。问所有任意两棵树的值的和是多少。

解题思路:

按照题意离散化,然后对H从大到小排序,这样可以保证前面的树高度都比当前的高(或者相等)。在计算的时候就可以使用当前的H。

POJ-1990类似

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
#include<vector>
#include<sstream>
#define lowbot(i) (i&(-i))
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct node
{
ll x, h, id;
}a[maxn], b[maxn];
bool cmp1(node a, node b)
{
return a.x < b.x;
}
bool cmp2(node a, node b)
{
return a.h < b.h;
}
bool cmp3(node a, node b)
{
return a.h > b.h;
}
int n;
void add(int x, int d, int tree[])
{
while(x <= n)
tree[x] += d, x += lowbot(x);
}
ll sum(int x, int tree[])
{
ll ans = ;
while(x)
ans += tree[x], x -=lowbot(x);
return ans;
}
int tree[maxn], tree_num[maxn];
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(a, , sizeof(a));
memset(b, , sizeof(b));
memset(tree, , sizeof(tree));
memset(tree_num, , sizeof(tree_num));
for(int i = ; i <= n; i++)
scanf("%lld%lld", &a[i].x, &a[i].h), a[i].id = i;
sort(a + , a + + n, cmp1);
for(int i = ; i <= n; i++)
{
if(a[i].x == a[i - ].x)b[a[i].id].x = b[a[i - ].id].x;
else b[a[i].id].x = i;
}
sort(a + , a + + n, cmp2);
for(int i = ; i <= n; i++)
{
if(a[i].h == a[i - ].h)b[a[i].id].h = b[a[i - ].id].h;
else b[a[i].id].h = i;
}
//for(int i = 1; i <= n; i++)
// cout<<b[i].x<<" "<<b[i].h<<endl;
sort(b + , b + + n, cmp3);
ll ans = , cnt, num;
for(int i = ; i <= n; i++)
{
cnt = sum(b[i].x, tree);
num = sum(b[i].x, tree_num);
ans += (num * b[i].x - cnt) * b[i].h;
cnt = sum(n, tree) - cnt;
num = i - num - ;
ans += (cnt - num * b[i].x) * b[i].h;
add(b[i].x, b[i].x, tree);
add(b[i].x, , tree_num);
}
cout<<ans<<endl;
}
return ;
}

最新文章

  1. 【Oracle】Oracle日期格式详解
  2. 剑指Offer面试题:33.二叉树的深度
  3. Javascript最简单的把html字符串编码的方法
  4. [UCSD白板题] Majority Element
  5. fastJSON☞JSONParameters☞时区的修改☞时间最后有一个&quot;Z&quot;
  6. [论文笔记] Methodologies for Data Quality Assessment and Improvement (ACM Comput.Surv, 2009) (2)
  7. Mahout
  8. Windows Cygwin Redis 安装(转)
  9. tcp并发服务端
  10. 搭建eclipse+tomcat开发环境
  11. Java基本包装类型
  12. Numpy三维数组的转置与交换轴
  13. Java流程控制语句
  14. Ubuntu云服务器下mysql授权远程登陆
  15. Spring Cloud(Dalston.SR5)--Eureka 注册中心搭建
  16. 【WIN10】移植opencc到WIN10-UWP,實現自己的繁簡轉換工具
  17. 玩转laravel5.4的入门动作(一)
  18. sudoers的权限被改,又忘记了root密码,又不能重启。这么做。
  19. PatBlt
  20. 点滴记录:input的value不能放值

热门文章

  1. linux安装php7
  2. java线程类图
  3. Cloudera Kudu是什么?
  4. $.get和$.post实例
  5. mysql关闭严格模式
  6. C#读写txt文件的方法
  7. maven课程 项目管理利器-maven 5-1 课程总结 1星(2018-11-08 07:19)
  8. intellijidea课程 intellijidea神器使用技巧 6-2 数据库关联
  9. Visual Studio Code 入门教程
  10. Thymeleaf基础知识