hdu4217 Data Structure?

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.

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.
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

Sample Output


   
   
   
   
    
    
    
    Case 1: 3

    
    
    
    Case 2: 14
    
    
    
     ， ， __int64，wa 。。
    
    
    
    
    
    
    
    #include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
__int64 sum;
struct node{
	int l,r,num;
}b[8*300000];

void build(int l,int r,int i)
{
	int mid;
	b[i].l=l;b[i].r=r;b[i].num=r-l+1;
	if(l==r)return;
	mid=(l+r)/2;
	build(l,mid,i*2);
	build(mid+1,r,i*2+1);
}

void question(int index,int i)
{
	int mid;
	if(b[i].l==b[i].r){
		sum+=b[i].l;
		b[i].num=0;return;
	}
	if(b[i*2].num>=index)question(index,i*2);
	else question(index-b[i*2].num,i*2+1);
	b[i].num=b[i*2].num+b[i*2+1].num;
}

int main()
{
	int n,m,i,j,T,num1=0,c;
	scanf("%d",&T);
	while(T--)
	{
		num1++;
		//printf("
",num1);
		scanf("%d%d",&n,&m);
		build(1,n,1);
		sum=0;
		for(i=1;i<=m;i++){
			scanf("%d",&c);
			question(c,1);	
		}
		printf("Case %d: %I64d
",num1,sum);
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

백준 알고리즘 14427번 : 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu4217 Data Structure?

좋은 웹페이지 즐겨찾기