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