洛谷P1160 队列安排 链表

洛谷P1160 队列安排   链表

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream>
 9 using namespace std ;
10
11 struct node{
12     int l,r ;
13 };
14 node a[100011] ;
15 int n,m,x,type,k ;
16 bool f[100011] ;
17
18 int main()
19 {
20     scanf("%d",&n) ;
21     f[ 1 ] = 1 ;
22     for(int i=2;i<=n;i++)
23     {
24         f[ i ] = 1 ;
25         scanf("%d%d",&x,&type) ;
26         a[ 0 ].l = 0 ;
27         a[ 0 ].r = 0 ;
28         if(type==0)
29         {
30             a[ i ].r = x ;
31             a[ i ].l = a[ x ]. l ;
32             a[ a[ i ].l ].r = i ;
33             a[ a[ i ].r ].l = i ;
34         }
35         else
36         {
37             a[ i ].l = x ;
38             a[ i ].r = a[ x ].r ;
39             a[ a[ i ].l ].r = i ;
40             a[ a[ i ].r ].l = i ;
41         }
42
43     }
44     scanf("%d",&m) ;
45     for(int i=1;i<=m;i++)
46     {
47         scanf("%d",&x) ;
48         if(!f[ x ]) continue ;
49         f[ x ] = 0 ;
50         a[ a[ x ].l ].r = a[ x ].r ;
51         a[ a[ x ].r ].l = a[ x ].l ;
52         a[ x ].l = 0 ;
53         a[ x ].r = 0 ;
54     }
55     for(int i=1;i<=n;i++)
56         if(f[ i ]&&!a[i].l)
57         {
58             k = i ;
59             break ;
60         }
61     printf("%d ",k) ;
62     while( a[ k ].r )
63         printf("%d ",a[ k ].r),k = a[ k ].r ;
64     return 0 ;
65 }
时间: 05-25

洛谷P1160 队列安排 链表的相关文章

洛谷 P1160 队列安排 Label:链表 不会

题目描述 一个学校里老师要将班上N个同学排成一列,同学被编号为1-N,他采取如下的方法: 1.先将1号同学安排进队列,这时队列中只有他一个人: 2.2-N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1-i -1中某位同学(即之前已经入列的同学)的左边或右边: 3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变. 在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号. 输入输出格式 输入格式: 输入文件arrange.in的第1行为一个正整数N

洛谷P1160 队列安排

题目描述 一个学校里老师要将班上N个同学排成一列,同学被编号为1-N,他采取如下的方法: 1.先将1号同学安排进队列,这时队列中只有他一个人: 2.2-N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1-i -1中某位同学(即之前已经入列的同学)的左边或右边: 3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变. 在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号. 输入输出格式 输入格式: 输入文件arrange.in的第1行为一个正整数N

洛谷 P1160 队列安排

题目描述 一个学校里老师要将班上N个同学排成一列,同学被编号为1-N,他采取如下的方法: 1.先将1号同学安排进队列,这时队列中只有他一个人: 2.2-N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1-i -1中某位同学(即之前已经入列的同学)的左边或右边: 3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变. 在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号. 输入输出格式 输入格式: 输入文件arrange.in的第1行为一个正整数N

P1160 队列安排

题目描述 一个学校里老师要将班上N个同学排成一列,同学被编号为1-N,他采取如下的方法: 1.先将1号同学安排进队列,这时队列中只有他一个人: 2.2-N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1-i -1中某位同学(即之前已经入列的同学)的左边或右边: 3.从队列中去掉M(M<N)个同学,其他同学位置顺序不变. 在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号. 输入输出格式 输入格式: 输入文件arrange.in的第1行为一个正整数N

[luogu p1160] 队列安排

传送门 题面 题目描述 一个学校里老师要将班上\(N\)个同学排成一列,同学被编号为\(1\sim N\),他采取如下的方法: 先将\(1\)号同学安排进队列,这时队列中只有他一个人: \(2-N\)号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为\(1\sim (i -1)\)中某位同学(即之前已经入列的同学)的左边或右边: 从队列中去掉\(M(M<N)\)个同学,其他同学位置顺序不变. 在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号. 输入输

洛谷P2365 任务安排 [解法二 斜率优化]

解法一:http://www.cnblogs.com/SilverNebula/p/5926253.html 解法二:斜率优化 在解法一中有这样的方程:dp[i]=min(dp[i],dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]) ) 其中min的后半部分,也就是dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]) 计算了将j~i分为一组的花费(以及提前计算的受影响花费) 设f(j)=dp[

洛谷 P2071 座位安排 seat.cpp/c/pas

P2071 座位安排 seat.cpp/c/pas 题目背景 公元二零一四年四月十七日,小明参加了省赛,在一路上,他遇到了许多问题,请你帮他解决. 题目描述 已知车上有N排座位,有N*2个人参加省赛,每排座位只能坐两人,且每个人都有自己想坐的排数,问最多使多少人坐到自己想坐的位置. 输入输出格式 输入格式: 第一行,一个正整数N. 第二行至第N*2+1行,每行两个正整数Si1,Si2,为每个人想坐的排数. 输出格式: 一个非负整数,为最多使得多少人满意. 输入输出样例 输入样例#1: 复制 4

[模板]洛谷T3369 普通平衡树 链表&amp;普通Treap

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<ctime> 6 #include<cmath> 7 #include<string> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 #

洛谷P2365 任务安排 [解法一]

题目描述 N个任务排成一个序列在一台机器上等待完成(顺序不得改变),这N个任务被分成若干批,每批包含相邻的若干任务.从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti.在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成).每个任务的费用是它的完成时刻乘以一个费用系数Fi.请确定一个分组方案,使得总费用最小. 例如:S=1:T={1,3,4,2,1}:F={3,2,3,3,4}.如果分组方案是{1,2}.{3}.{4