POJ 2182 Lost Cows(树状数组,暴力解法)-程序员宅基地

技术标签: 数据结构--树状数组  ACM--题解汇总  ACM--技巧题  ACM  

POJ 2182 Lost Cows(树状数组,暴力解法)

http://poj.org/problem?id=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. 

Input

* Line 1: A single integer, N 
* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on. 

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

分析:

       其实这道题目只要会手算用例就能暴力解决。

       假设读入题目给的数组a[n],其中a[1]=0

       这道题目只给出了在i之前且比位于第i个位置的值小的值有多少个,我们在纸上分析用例可知,最后一个数的值肯定是a[n]+1.

       然后我们从后往前推,且初始化一个数组vis[n]为全1。vis[i]==1表示当前值为i的数还没出现。首先我们推出最后一个数的值为a[n]+1,所以我们标记vis[a[n]+1]=0,接着我们推n-1的值,假设a[n-1]=3,那么就是在n-1的数之前有3个还未出现的数比它小,那么我们从vis[1]开始扫描,找到第4个1的位置就是a[n-1]的值。然后把这第4个1的位置vis[x]标记0.接下去找n-2位置的值,以此类推即可。

AC代码:266ms

<span style="font-size:18px;">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =10000;
int a[MAXN];//初始
int vis[MAXN];//标记1
int ans[MAXN];//最终计算的结果
int main()
{
    int n;
    while(scanf("%d",&n)==1&&n)
    {
        a[1]=0;
        for(int i=2;i<=n;i++)
            scanf("%d",&a[i]);

        for(int i=1;i<=n;i++)
            vis[i]=1;
        ans[n]=a[n]+1;
        vis[ans[n]]=0;
        for(int i=n-1;i>=1;i--)
        {
            int num = a[i];
            int j;
            for(j=1;i<=n;j++)
            {
                if(vis[j]==1)
                {
                    num--;
                    if(num<0)
                    {
                        vis[j]=0;
                        break;
                    }
                }
            }
            ans[i]=j;
        }
        for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}</span>

 

解法二:树状数组。初始时,树状数组为全0.sum(x)表示已经确定了值的且小于等于x的值的个数。

我们依然从后往前倒推,对于当前考虑的a[n],假设它的值为x,那么我们就执行add(x,1)。接下来我们要找到a[n-1]的值y,y肯定在[1,8000]范围内,所以可以用二分查找确定y的值。如果我们猜y=8的话,如果a[n-1]=4并且比8小的已经确定了的值即sum(7)=3,可以说明从1到7中:由有3个数的值已经确定了 并且 还有4个值没有确定且这些没确定值的比y小的数正好是4个,那么y肯定>=8。可以加大y的范围继续探测。如果sum(7)+4<7的话,8就比y本来的值要大了。

如果sum(7)+4>7的话,8就比y本来的值要小。

       由此可得一般结论,我们猜测当前a[i]的值为y,如果

Sum(y-1)+a[i]==y-1 那么y为最小值

Sum(y-1)+a[i]<y-1 那么y-1为最大值

Sum(y-1)+a[i]>y-1 那么y+1为最小值

 

AC代码:0ms 注意if else语句的顺序,发生概率大的语句放前面。

 

<span style="font-size:18px;">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =8008;
int a[MAXN];//初始
int ans[MAXN];//最终计算的结果
int c[MAXN];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x)
{
    int res=0;
    while(x)
    {
        res +=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}

int main()
{

    while(scanf("%d",&n)==1&&n)
    {
        a[1]=0;
        memset(c,0,sizeof(c));
        for(int i=2;i<=n;i++)
            scanf("%d",&a[i]);

        ans[n]=a[n]+1;
        add(a[n]+1,1);
        for(int i=n-1;i>=1;i--)
        {
            int L=1,R=n;
            while(R>L)
            {
                int mid = (R+L+1)/2;
                if(sum(mid-1)+a[i] < mid-1)//这3个if else语句的顺序换一换 时间就可能是16ms 63ms 0ms等
                    R=mid-1;
                else if(sum(mid-1)+a[i] == mid-1)
                    L=mid;
                else
                    L=mid+1;
            }
            ans[i]=L;
            add(ans[i],1);
        }
        for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}
</span>

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u013480600/article/details/21574467

智能推荐

java 画笔 粗细_java中如何设置线条的粗细例题?-程序员宅基地

文章浏览阅读2.2k次。展开全部Java线条粗细32313133353236313431303231363533e58685e5aeb931333337386665一般要使用java Swing方面的知识importjavax.swing.*;importjava.awt.*;importjava.awt.geom.*;publicclassExample6_5extendsJFrame{publicEx..._javafx line粗细

[210923]操作系统(自考)重点笔记_必须根据分配给程序的内存区域对程序中指令 和数据的存储地址进行重定位,即要把-程序员宅基地

文章浏览阅读2.0k次,点赞5次,收藏43次。操作系统(自考)引导参考资源你当初是如何学会操作系统这门课程的? - happywei的回答 - 知乎如何学好操作系统原理这门课? - 程序员cxuan的回答 - 知乎哈尔滨工业大学 - 操作系统-MOOC应试技巧 * *简答题综合题进程调度送分题。关键:弄懂进程调度算法的规则、周转时间的计算方法(结束时间-达到时间)PV操作磁盘优化移臂调度页面调度PV操作概论/运行环境 *OS基本概念从定义、特征、功能、体系结构(*)、分类、设计(*)6个方_必须根据分配给程序的内存区域对程序中指令 和数据的存储地址进行重定位,即要把

小学生该学什么编程语言入门?-程序员宅基地

文章浏览阅读3w次。【原始问题】孩子小学6年级,对编软件感兴趣,说上初中学函数以后,打算学习编软件,但是我不懂啊,无法指导。有懂这方面的,可否指点一二,从什么地方入手?再有就是为啥我建议娃学习Python, 而不是Scratch呢?我觉得MIT的Scratch虽然很不错,但是它不够抽象化,不是一个真正的通用的编程语言。5,6岁的小小娃学scratch还行,大娃还是应该学真正的general pur

halcon基于形状的几何定位算子选择_find_scaled_shape_models 详解-程序员宅基地

文章浏览阅读1.3k次。一,几何定位的算子选择不支持缩放的几何定位。根据模版图像创建模版create_shape_model ()find_shape_model ()find_shape_models ()clear_shape_model()根据XLD轮廓创建模版create_shape_model_xld()find_shape_model ()find_shape_models ()c..._find_scaled_shape_models 详解

ionic tabs_tabs ionic-程序员宅基地

文章浏览阅读417次。https://ionicframework.com/docs/ionicons/搜索图标原文链接:http://blog.maptoface.com/post/124_tabs ionic

Java统一异常处理--实战篇-程序员宅基地

文章浏览阅读4k次,点赞2次,收藏20次。文章目录背景什么是统一异常处理目标统一异常处理实战用 Assert(断言) 替换 throw exceptionAssert善解人意的Enum定义统一异常处理器类异常处理器说明handleServletExceptionhandleBindExceptionhandleValidExceptionhandleBusinessException、handleBaseExceptionhandleException异于常人的404统一返回结果验证统一异常处理主要代码开始验证捕获自定义异常捕获进入 Control_java统一异常处理

随便推点

CodeForces 982 C Cut 'em all!-程序员宅基地

文章浏览阅读62次。Cut 'em all!题意:求删除了边之后,剩下的每一块联通块他的点数都为偶数,求删除的边最多能是多少。题解:如果n为奇数,直接返回-1,因为不可能成立。如果n为偶数,随意找一个点DFS建树记录下他的子孙+本身的个数。然后再DFS一下,对于每一个点,他的个数为偶数,就把他与父节点的边隔断, cnt++。 最后cnt就是答案。代码: 1 #include<bits/s...

zabbix-agent key属性列表_system.hw.cpu[<cpu>,<info>]-程序员宅基地

文章浏览阅读5.4w次。Key描述返回值参数详细说明agent.hostname返回被监控端名称字符串-返回配置文件中配置的被监控端的名称agent.ping检测被监控端是否存活1 - 运行中 其他 - 未运行-使用函数 nodata()检测客户端是否正在运行_system.hw.cpu[,]

Qt下libusb-win32的使用方法(转)-程序员宅基地

文章浏览阅读147次。源:Qt下libusb-win32的使用方法之前一直找不到适合WIN7下的Tiny6410的USB下载软件,正好这几天开始学习USB,所以打算自己写一个专门用于Tiny6410的WIN7下的USB下载软件。 发现了libusb这个库可以用作无驱USB开发,就是说根本不需要了解Window驱动开发的知识就可以开发USB设备驱动,只需要了解一下USB的相关协议即可。Wi..._qt win32 libusb库

HTML+CSS+JS实现 ️制作loading动画效果️_js实现好看的loading效果-程序员宅基地

文章浏览阅读1.1k次,点赞3次,收藏9次。???? 作者主页:Java李杨勇???? 简介:Java领域优质创作者????、Java李杨勇公号作者 简历模板、学习资料、面试题库、技术互助【关注我,都给你】???? 欢迎点赞 ???? 收藏 留言 ???? 效果演示:文末获取源码代码目录:主要代码实现:CSS样式:.load1 .loader,.load1 .loader:before,.load1 .loader:after { background: #FFF; -w_js实现好看的loading效果

嵌入式基础知识总结_嵌入式软件基础知识点总结-程序员宅基地

文章浏览阅读7.2k次,点赞16次,收藏80次。提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、选择题二、填空题三、简答题四、综合题2.读入数据总结前言 本篇为嵌入式知识点总结,花费了大概一两天时间整理的,现在分享给大家!!!一、选择题1.以下哪个不是嵌入式系统的特点?( )A.面向特定应用 B.高质量高可靠 C.可裁剪性 D.具备二次开发能力 解析:嵌入式系统本身不具备二次开发能力,即_嵌入式软件基础知识点总结

[学习] 鸿洋大大的万能适配器(1)_鸿洋 commonadapter-程序员宅基地

文章浏览阅读953次。总结一下从 ViewHolder 开始学习public ViewHolder(Context context, View itemView) { super(itemView); mContext = context; mConvertView = itemView; mViews = new SparseArra..._鸿洋 commonadapter

推荐文章

热门文章

相关标签