Data Structure?
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2166 Accepted Submission(s): 692
Problem Description
Data structure is one of the basic skills for Computer Science students, which is a particular way of storing and organizing data in a computer so that it can be used efficiently. Today let me introduce a data-structure-like problem for you.
Original, there are N numbers, namely 1, 2, 3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.
Original, there are N numbers, namely 1, 2, 3...N. Each round, iSea find out the Ki-th smallest number and take it away, your task is reporting him the total sum of the numbers he has taken away.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.
Each test case includes two integers N, K, K indicates the round numbers. Then a line with K numbers following, indicating in i (1-based) round, iSea take away the Ki-th smallest away.
Technical Specification
1. 1 <= T <= 128
2. 1 <= K <= N <= 262 144
3. 1 <= Ki <= N - i + 1
Output
For each test case, output the case number first, then the sum.
Sample Input
2 3 2 1 1 10 3 3 9 1
Sample Output
Case 1: 3 Case 2: 14
Author
iSea@WHU
Source
不知道为什么。。。我用long long 交到GCC编译器上就是一直wa。 然后改__int64才过掉的。。
//
// 4217.cpp
// ACM_HDU
//
// Created by ipqhjjybj on 13-9-8.
// Copyright (c) 2013年 ipqhjjybj. All rights reserved.
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define lowbit(x) (x&(-x))
const int MAXN=333333;
int n,k;
int a[MAXN];
#define LL __int64
void Update(int pos){
while(pos<=n){
a[pos]--;
pos+=lowbit(pos);
}
}
int Query(int pos){
int sum=0;
while(pos>0){
sum+=a[pos];
pos-=lowbit(pos);
}
return sum;
}
int Bisearch(int k){
int l=1,r=n,mid;
while(l<r){
mid=(l+r)>>1;
if(Query(mid)>=k)
r=mid;
else l=mid+1;
}
return l;
}
int main(){
int t,tmp,tt=0;
LL sum;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&k);
sum=0;
for(int i=0;i<=n;i++)
a[i]=lowbit(i);
while(k--){
scanf("%d",&tmp);
tmp=Bisearch(tmp);
Update(tmp);
sum+=tmp;
}
cout<<"Case "<<++tt<<": "<<sum<<endl;
//printf("Case %d: %lld\n",++tt,sum);
}
return 0;
}
我原本的查找代码：
int Bisearch(int k){
int l=1,r=n,mid;
while(l<=r){
mid=(l+r)>>1;
int tmp=Query(mid)+mid;
if(tmp==k){
return mid;
}else if(tmp<k){
l=mid+1;
}else r=mid-1;
}
return l;
}
在这题是错误的 。 因为它没有考虑到这样的情况。 假设第8个数据是0，这样前7个数据跟前8个数据和是相等的。 这样我们就可能查找到错误的8了。
所以，我们要保证查找到的是最左边的前tmp项和＝＝k。。 这里我wa了好多次。