树状数组不太会留下慢慢看

2011年3月

日

一

二

三

四

五

六

统计

随笔 - 29
文章 - 0
评论 - 2
引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

阅读排行榜

评论排行榜

L2B的演唱会

Description

著名乐队L2B宣布要在Music岛举办一场演唱会，售票当天那家伙，那场面，相当热闹，真是锣鼓喧天，鞭炮齐鸣，旌旗招展，人山人海啊。
L2B的粉丝小C得知消息，飞奔到售票处，却发现买票的人已经排起了长龙的队伍，正当他万般绝望的时候，他看到了敬爱的PengSir，于是他向PengSir请求帮助。PengSir嘴角微微一笑，说道：票我倒是可以给你一张，可是白给的话就太没意思了，这样吧，我有一个问题考考你，如果你能在5秒钟内答出来的话，我就送你这张票，怎么样？小C急不可待的说：没问题。于是PengSir徐徐说道：这里排队的一共有N个人，每个人之前都发了一个号码牌（数字从1到N各不相同），我们假定队头是前，队尾是后，每个人P最多能够买的票数是在这个人后面而且号码牌的数字比这个人P的数字小的人数总和。我的问题是，告诉你每个人手中的号码，你来算出今天最多一共能卖出去多少张票S么？
举个例子说吧
假设我们现在有10个人在排队，他们手中的号码分别是2 5 8 7 6 1 9 4 10 3，那么可以很快算出他们最多可以买的票数分别是1 3 5 4 3 0 2 1 1 0，所以最多一共能卖出去1+3+5+4+3+0+2+1+1+0=20张票。怎么样？明白了吧？
小C听完，顿时傻眼，亲爱的朋友，你能帮助小C来实现自己心愿吗？

Input

输入有多个测试用例
每个测试用例的第一行是正数N（ 0 < N <= 30000 ），
第二行是N个整数Ai（ 0 < Ai <= N ），且每个Ai出现且仅出现一次，每两个相邻的整数之间有且仅有一个空格隔开

Output

对于每一个测试用例，只输出一个整数S

Sample Input

10
2 5 8 7 6 1 9 4 10 3

Sample Output

#include <iostream>
2

#include<string.h>
3

#include<stdio.h>
4

using namespace std;
5

const int N=30010;
6

int t[N],a[N],n;
7

void add(int x)
8

{
9

for(;x<=n;x+=x&-x)
10

t[x]+=1;
11

}
12

int sum(int x)
13

{
14

int ans=0;
15

for(;x>0;x-=x&-x)
16

ans+=t[x];
17

return ans;
18

}
19

int main()
20

{
21

while(~scanf("%d",&n))
22

{
23

int i;
24

memset(t,0,sizeof(t));
25

for(i=1;i<=n;i++)
26

scanf("%d",&a[i]);
27

int ans=0;
28

for(i=n;i>=1;i--)
29

{
30

ans+=sum(a[i]);
31

add(a[i]);
32

}
33

printf("%d\n",ans);
34

}
35

return 0;
36

}
37

posted on 2011-03-06 22:19 Yiner 阅读(299) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

Yiner的ACM

统计