首页 > ACM题库 > HDU-杭电 > HDU 3149-Tetrahedral Stacks of Cannonballs-分治-[解题报告]HOJ
2014
03-06

HDU 3149-Tetrahedral Stacks of Cannonballs-分治-[解题报告]HOJ

Tetrahedral Stacks of Cannonballs

问题描述 :

Code Permutations    Code Permutations
WALL.ETM, as he cleans up and organizes the depopulated Earth, has come upon some Civil War memorials. He is consolidating the cannonballs into one location, and decides to use pyramids with triangular bases rather than ones with square bases.

In Civil War memorials with cannons and stacks of cannonballs, the cannonballs were sometimes stacked as a four-sided pyramid, with the base as a square of cannonballs with n balls on each side. An alternative is to stack them in a three-sided pyramid, which is in fact one of the Platonic solids, a tetrahedron.

This tetrahedron of cannonballs has a base that is an equilateral triangle of cannonballs with n balls on each side. The number of balls in that triangle is given simply by adding together the numbers from 1 to n. On top of each layer (starting from the base) is a triangle with one less ball on each side, up to the top-most layer with a single ball.

Given the number of cannonballs on each side of the base, compute the total number of cannonballs in the entire tetrahedral stack.

输入:

The first line contains a single number n, giving the number of tetrahedral problems posed, for a maximum of 100 problems. Following that are exactly n lines, each with a single number giving the number of cannonballs on each side of the base for a tetrahedron of cannonballs, a number greater than 0 and less than 1000.

输出:

The first line contains a single number n, giving the number of tetrahedral problems posed, for a maximum of 100 problems. Following that are exactly n lines, each with a single number giving the number of cannonballs on each side of the base for a tetrahedron of cannonballs, a number greater than 0 and less than 1000.

样例输入:

6
1
2
3
5
27
999

样例输出:

1: 1 1
2: 2 4
3: 3 10
4: 5 35
5: 27 3654
6: 999 166666500

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=3149

分治法求两个等长有序数组的中位数。

使用分治法复杂度可以从O(n)降到O(logn)。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

#define Maxn 300005
int median(int *a,int *b,int length)
{
    if(length == 1) return a[0] < b[0] ? a[0] : b[0];
    int mid = (length - 1)/2;
    if(a[mid] == b[mid]) return a[mid];
    if(a[mid] < b[mid])
    {
        return median(&a[length - mid -1],b,mid+1);
    }
    else
    {
        return median(a,&b[length - mid -1],mid+1);
    }
}

int a[Maxn],b[Maxn];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int t;
    int n;
    int A,B,C,D;
    int q;
    int len;
    scanf(" %d",&t);
    while(t--)
    {
        scanf(" %d",&n);
        for(int i=0; i<n; i++) scanf(" %d",&a[i]);
        for(int i=0; i<n; i++) scanf(" %d",&b[i]);
        scanf(" %d",&q);
        for(int i=0; i<q; i++)
        {
            scanf(" %d %d %d %d",&A,&B,&C,&D);
            len = B-A+1;
            int ans = median(a+A,b+C,len);
            printf("%d\n",ans);
        }
    }
    return 0;
}

关于其中的原理解释以及如何求解两个不同长度数组间的中位数请参考博客:http://blog.csdn.net/Hackbuteer1/article/details/7584838

参考:http://blog.csdn.net/niuox/article/details/9050443


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯