Yiner的ACM

成长的痕迹
<2011年2月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

统计

  • 随笔 - 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 阅读(307) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理