题目解析
将给定n个火车的序列，问最少需要多少个轨道才能使火车从小到大排好序
解题思路
如何安排呢？
- 最简单的就是 我往死里排 能排下就排
- 也就是当前火车比之前安排到轨道的火车短 那么我就将这辆火车安排到他的前面
代码
贪心
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();// 输入
boolean f = false;
for (int j = 0; j < cnt; j++)
{
if (a < shu[j])// 已有数组里面有比a大的数则赋值
{
shu[j] = a;
f = true;
break;
}
}
if (!f)// 没有则再开一条
{
shu[cnt] = a;
cnt++;// 个数+1
}
}
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;
}
}
超时1、3
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]; // dp[i]表示第shu[i]个元素为末尾的最长子序列，最短是自己
int max = 0;
for (int i = 0; i < n; i++)
{
shu[i] = ini();// 输入数据
dp[i] = 1;
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;
}
}
超时1、2、3
二分
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， 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;
}
}