Lost Cows（线段树） POJ - 2182

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

题意：给出n头牛前面有多少头比他编号少的数目，求出原来的牛的编号，

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include<set>
#include 
#include
#include    
#include
#include
#include
using namespace std;
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 100000005    
int tree[maxn] = {};
int a[maxn] = {};
int b[maxn] = {};
void buildTree(int step,int L,int R)//建树
{
    if (L == R)
    {
        tree[step] = 1;
        return;
    }
    int mid = (L + R) >> 1;
    buildTree(step * 2, L, mid);
    buildTree(step * 2 + 1, mid + 1, R);
    tree[step] = tree[step * 2] + tree[step * 2 + 1];
}
int search(int step, int L, int R, int num)
{
    tree[step]--;//更新，当前位置减一
    if (L == R)
    {
        return L;
    }
    int mid = (L + R) / 2;
    if (num <= tree[step * 2])//在左子树范围
        search(step * 2, L, mid, num);
    else
        search(step * 2 + 1, mid + 1, R, num-tree[step*2]);//在右子树范围，减去左子树的个数
}
int main()
{
    int n;
    scanf("%d", &n);
    buildTree(1, 1, n);
    for (int i = 2; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    a[1] = 0;
    for (int i = n; i >= 1; i--)//从后往前找，只有最后一个是确定的
    {
        b[i] = search(1, 1, n, a[i] + 1);//查找编号时要加一
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", b[i]);
    }
}

ACM

Lost Cows（线段树） POJ - 2182

题意：给出n头牛前面有多少头比他编号少的数目，求出原来的牛的编号，

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签