本文作者:ljh2000 
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

题目链接: http://uoj.ac/contest/36/problem/278

正解:排序...

解题报告:

  考场上我是make了几组数据,然后用暴力跑跑才发现的结论...

  比如说:显然2只能由1转移过来,3只能由2转移过来,并且,相同权值的话,最后一个显然是最小的,不然就可以再加一了呀...

  所以按权值为第一关键字(从小到大),下标为第二关键字(从大到小)排序,依次编号即可。我在考场上写的是线性做法,就是对于每个权值挂个链就ok了。

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
int n,f[MAXN],a[MAXN],cnt;
int ecnt,first[MAXN],to[MAXN],next[MAXN]; inline void link(int x,int y){
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;
} inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
} inline void work(){
n=getint(); for(int i=1;i<=n;i++) a[i]=getint(),link(a[i],i);
cnt=0;
for(int i=1;i<=n;i++) {
if(first[i]==0) break;
for(int j=first[i];j;j=next[j]) {
a[to[j]]=++cnt;
}
}
for(int i=1;i<=n;i++) printf("%d ",a[i]);
} int main()
{
work();
return 0;
}

  

最新文章

  1. KnockoutJS 3.X API 第七章 其他技术(7) 微任务
  2. MySQL - 问题集 - 触发器更新本表数据异常&quot;Can’t update table ‘tbl’ in stored function/trigger because it is already used by statement which invoked this&quot;
  3. 约瑟夫环问题(c++)
  4. BZOJ 4384: [POI2015]Trzy wieże
  5. 如何实现在已有代码之后添加逻辑之java动态代理
  6. java三线程循环有序打印ABC
  7. 要理解javascript中间apply和call
  8. Android Afinal框架学习(二) FinalActivity 一个IOC框架
  9. .NET Core 在程序集中集成Razor视图
  10. 【Java编程】Java中的字符串匹配
  11. PAT1061:Dating
  12. boost::bind 介绍
  13. eclipse2019-03设置代码编辑区背景为图片
  14. NSNotification相关
  15. python基础一数据类型之集合
  16. [转]操作MySQL数据库报出:Parameter index out of range (1 &gt; number of parameters, which is
  17. Metro Revealed: Building Windows 8 apps with XAML and C# 阅读笔记
  18. Java多线程相关的
  19. EasyUI-Tooltip(提示框)学习
  20. android 源码编译及其运行模拟器相关问题记录

热门文章

  1. Shell计算器
  2. Python基础之初识递归
  3. 关于Java静态代码块、初始化块、构造函数的调用顺寻问题?
  4. 【Caffe】caffemodel的大小计算(转载)
  5. linux使用rsync+inotify-tools+ssh实现文件实时同步
  6. 打造自己的LINQ Provider(上):Expression Tree揭秘
  7. springMVC的注释集合
  8. jquery获取页面iframe内容
  9. task15-18
  10. MATLAB循环结构:for语句+定积分实例