hdu 4217 线段树
题目大意： t 组测试，每组测试有 n 个数（1～n），有 k 次循环，每次取出第k小的数，求所有取出的数字之和。
[cpp]
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define SIZE 262145
using namespace std;
int array[SIZE<<1];
void creat(int left,int right,int root)
{
int m;
array[root] = right-left+1;//每个节点记录包含的数字个数
if(left == right){
return;
}
m=(right+left)/2;
creat(left,m,root<<1); //array[root]的左孩子为array[2*root]
creat(m+1,right,root<<1|1); //array[root]的右孩子为array[2*root+1]
}
int Del(int left,int right,int root,int key)
{
int m,flag;
array[root]--;
if(left == right){
return right;
}
m=(right+left)/2;
if(key<=array[root<<1]){//左子树的叶子节点数大于key
flag=Del(left,m,root<<1,key);
}
else{
key-=array[root<<1];//在右子树中找，key要减去左子树包含的叶子节点数
flag=Del(m+1,right,root<<1|1,key);
}
return flag;
}
int main()
{
int t,n,k,kk,i,j;
long long sum;
scanf("%d",&t);
for(i=1;i<=t;i++){
sum=0;
scanf("%d%d",&n,&k);
creat(1,n,1);
for(j=0;j<k;j++){
scanf("%d",&kk);
sum+=Del(1,n,1,kk);
}
printf("Case %d: %lld\n",i,sum);
}
return 0;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define SIZE 262145
using namespace std;
int array[SIZE<<1];
void creat(int left,int right,int root)
{
int m;
array[root] = right-left+1;//每个节点记录包含的数字个数
if(left == right){
return;
}
m=(right+left)/2;
creat(left,m,root<<1); //array[root]的左孩子为array[2*root]
creat(m+1,right,root<<1|1); //array[root]的右孩子为array[2*root+1]
}
int Del(int left,int right,int root,int key)
{
int m,flag;
array[root]--;
if(left == right){
return right;
}
m=(right+left)/2;
if(key<=array[root<<1]){//左子树的叶子节点数大于key
flag=Del(left,m,root<<1,key);
}
else{
key-=array[root<<1];//在右子树中找，key要减去左子树包含的叶子节点数
flag=Del(m+1,right,root<<1|1,key);
}
return flag;
}
int main()
{
int t,n,k,kk,i,j;
long long sum;
scanf("%d",&t);
for(i=1;i<=t;i++){
sum=0;
scanf("%d%d",&n,&k);
creat(1,n,1);
for(j=0;j<k;j++){
scanf("%d",&kk);
sum+=Del(1,n,1,kk);
}
printf("Case %d: %lld\n",i,sum);
}
return 0;
}
补充：软件开发 , C++ ,
