7-2 列车调度

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：
输入第一行给出一个整数N (2 ≤ N ≤10
​5
​​ )，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：
9
8 4 2 5 3 9 1 6 7

输出样例：
4

思路：首先明确的一点就是每条轨道上可以停放多组列车！！！然后就是增加轨道的前提就是所有轨道的最后一位列车的序号均小于当前入轨道的列车序号！！！根据这个原理，可知最新添加的轨道的最后一位一定比前面的所有轨道的最后一位大。当有列车入队时，应该优先添加到上层的队，因此需要遍历循环一下找到最合适的轨道，但是如果循环遍历的话会有两个测试点超时，因此采用二分法进行寻找插入的轨道。具体的代码如下所示

此代码为循环遍历找插入点：

#include<stdio.h>
int main()
{
	int count=1,i,j,n;
	scanf("%d",&n);
	int a[n],b[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
	}
	a[0]=b[0];
	for(i=1;i<n;i++)
	{
	 for(j=0;j<count;j++)
	 {
	 	if(b[i]<a[j])
	 	{
	 		a[j]=b[i];
	 		break;
		 }
		else if(j==(count-1))
		 {
		 	a[count]=b[i];
		 	count++;
		 	break;
		 }
	 }
    }  
    printf("%d",count);
}

此代码为二分法：

#include<stdio.h>
int main()
{
	int count=1,i,j,n;
	scanf("%d",&n);
	int a[n],b[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
	}
	a[0]=b[0];
	for(i=1;i<n;i++)
	{
		if(b[i]>a[count-1])
		{
			a[count]=b[i];
			count++;	
		} 
		else 
		{
			int l=0, r=count-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(a[mid]>b[i])
                    r=mid-1;
                else l=mid+1;
            }
            a[l]=b[i];
		}
    }  
    printf("%d",count);
}

L2-014 列车调度

题目描述：
火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（ Entrance ）轨道和一条出口（ Exit ）轨道，它们之间有 N 条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{ 8 ， 4 ， 2 ， 5 ， 3 ， 9 ， 1 ， 6 ， 7 }的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：
输入第一行给出一个整数 N ( 2 ≤ N ≤ 10 ^​ 5 )，下一行给出从 1 到 N 的整数序号的一个重排列。数字间以空格分隔。

输出格式：
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：
9
8 4 2 5 3 9 1 6 7

输出样例：
4

这题emmmm…
这题可以看为最长上升子序列问题，只不过普通的贪心与dp都超时罢了。/哭笑

贪心

import java.io.*;
import java.math.*;
import java.util.*;

public class Main
{

	public static void main(String[] args) throws IOException
	{
		int n = ini();
		int shu[] = new int[n + 10];
		int cnt = 0;// 统计个数
		for (int i = 0; i < n; i++)
		{
			int a = ini();// 输入
			int f = 0;
			for (int j = 0; j < cnt; j++)
			{
				if (a < shu[j])// 已有数组里面有比a大的数则赋值
				{
					shu[j] = a;
					f = 1;
					break;
				}
			}
			if (f == 0)// 没有则再开一条
			{
				shu[cnt] = a;
				cnt++;// 个数+1
			}
		}
//		out.println(Arrays.toString(shu));
		out.println(cnt);

		out.flush();
		out.close();

	}

	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

}

dp

import java.io.*;
import java.math.*;
import java.util.*;

public class Main
{

	public static void main(String[] args) throws IOException
	{
		int n = ini();
		int shu[] = new int[n];
		int dp[] = new int[n];
		int max = 0;
		for (int i = 0; i < n; i++)
		{
			shu[i] = ini();// 输入数据
			dp[i] = 1;// dp[i]表示第shu[i]个元素为末尾的最长子序列，最短是自己
			for (int j = 0; j < i; j++)// 从他前面开始试探
			{
				if (shu[j] <= shu[i])// 前面有比我小的数我就取他的长度+1
					dp[i] = Math.max(dp[i], dp[j] + 1);// 在j的基础上多一个
			}
			max = Math.max(max, dp[i]);// 记录最大的
		}
		out.println(max);

		out.flush();
		out.close();

	}

	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

}

看了大佬们的这题才晓得最长上升子序列问题还可以贪心的二分来，真的越学越感觉自己的渺小啊！

import java.io.*;
import java.math.*;
import java.util.*;

public class Main
{

	public static void main(String[] args) throws IOException
	{
		int n = ini();
		int shu[] = new int[n + 10];
		int len = 0;
		for (int i = 0; i < n; i++)
		{
			int a = ini();
			if (len == 0 || shu[len - 1] < a)
				// 将第一辆车开入一个轨道
				// 或者将现在的车大于前面的车车就排到后面
				shu[len++] = a;
			else
			{
				// 现在的轨道中里面车车已经是从大到小的了
				// 所以直接上二分
				int l = 0;
				int r = len - 1;
				while (l < r)
				{
					int mid = (l + r) / 2;// 中点
					if (shu[mid] > a)
						// 中间的数比输入的数小
						// 则修改左端点为中点
						r = mid;
					else
						// 中间的数比输入的数大
						// 则修改右端点为中点
						l = mid + 1;
				}
				shu[l] = a;
				// 左右端点重合的时候将a赋值赋值给这个轨道
//					System.out.println(l + "   " + shu[l]);
				// 可以这里把注释去掉看看哦，理解理解一下哦
				// printf大法非常棒的哦
			}
		}
		out.println(len);

		out.flush();
		out.close();

	}

	static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);

	static int ini() throws IOException
	{
		sc.nextToken();
		return (int) sc.nval;
	}

}

二分查找

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

闪现

Description

Input

Output

Sample Input

Sample1:
3
1 2 3
Sample2:
9
1 3 2 4 8 6 9 5 7

Sample Output

Sample1:
3
Sample2:
5

Data Constraint

Solution

最长不下降子序列(N log N)或者直接set暴力模拟再用权值线段树或splay维护即可。

Code1

#include<cstdio>
#include<cstring>
#include<set>
#include<cmath>
#include<algorithm>
#define inf 2147483647
#define N 100010
using namespace std;
int n,x,ans;
multiset<int> t;
multiset<int>::iterator it;
int main(){
    scanf("%d",&n);
    t.insert(inf);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        it=t.lower_bound(x);
        if(*it==inf) ans++;
        else t.erase(it);
        t.insert(x);
    }
    printf("%d",ans);
    return 0;
}

Code2

var
    i,n,l,r,mid,op,ss:longint;
    a,b:array[1..100000]of longint;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do
    begin
        if (op=0)or(a[i]>b[op])then
        begin
            inc(op);
            b[op]:=a[i];
        end
        else
        begin
            l:=1;
            r:=op;
            ss:=0;
            while l<=r do 
            begin
                mid:=(l+r)div 2;
                if a[i]<b[mid] then
                begin
                    ss:=mid;
                    r:=mid-1;
                end
                else l:=mid+1;
            end;
            b[ss]:=a[i];
        end;
    end;
    writeln(op);
end.

作者：zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81843096