Yiner的ACM

成长的痕迹
<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

  • 随笔 - 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

20
 1#include <iostream>
 2#include<string.h>
 3#include<stdio.h>
 4using namespace std;
 5const int N=30010;
 6int t[N],a[N],n;
 7void add(int x)
 8{
 9    for(;x<=n;x+=x&-x)
10        t[x]+=1;
11}

12int sum(int x)
13{
14    int ans=0;
15    for(;x>0;x-=x&-x)
16        ans+=t[x];
17    return ans;
18}

19int 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 阅读(191) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理