题解 | #合唱队#
合唱队
http://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
/*最长上升子序列问题
中间最高，向两边逐渐减小（相等也不行）。不要求最高的同学左右人数必须相等。
不允许改变队列元素的先后顺序，也就是说，只能剔除不能排序。
计算最少需要出列几名同学满足以上要求，也就是说，剔除某些同学，剩下的队列自然而然的满足要求
（1）计算出每个同学左边最多有几个人满足从左到右依次增大的序列要求（包括自己）。
示例：186 186 150 200 160 130 197 200
1 1 1 2 2 1 3 4
动态方程：
（2）计算出每个同学右边最多有几个人满足从右到左依次增大的序列要求（包括自己）。
示例：186 186 150 200 160 130 197 200
3 3 2 3 2 1 1 1
动态方程：
（3）将左右最多序列人数相加减一（自己加了两遍），就得到以该数为中心时，所在队列最多人数。
然后依次算出所有的队列的最多人数，然后与总人数相减，其中最小值就是最少剔除人数。
总人数-该数所在队列人数=需要出队的人数
*/
#include <stdio.h>
#include <string.h>
int main(){
int n, row[3000], Max;
char lmax[3000],rmax[3000];
while(scanf("%d",&n) != EOF){
//初始化
memset(lmax,1,3000);
memset(rmax,1,3000); //初始就自己一人，所以初始值为1
Max = 0; //记录最大序列人数
//读数据
for(int i = 0; i < n; i++){
scanf("%d",&row[i]);
}
//计算各数左侧最长上升序列
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(row[j] < row[i] && lmax[i] < lmax[j] + 1){
lmax[i] = lmax[j] + 1;
}
}
}
//计算各数右侧最长上升序列
for(int i = n - 2; i >= 0; i--){
for(int j = n - 1; j > i; j--){
if(row[j] < row[i] && rmax[i] < rmax[j] + 1){
rmax[i] = rmax[j] + 1;
}
}
}
//计算最少剔除人数 = n - (lmax[i] + rmax[i] - 1)
for(int i = 0; i < n; i++){
int tmp =lmax[i] + rmax[i] - 1;
if(Max < tmp) Max = tmp;
}
printf("%d\n",n - Max);
}
return 0;
}
/*最长上升子序列问题
二分搜索法：将最长上升子序列存储起来，使用二分法进行插入覆盖求取
将要查找的数取出来，与已有序列（max位）进行比对，寻找该数次大于的数，最长子序列就为i+1
小于·
左次小于
右次小于
*/
#include <stdio.h>
#include <string.h>
int main(){
int n, row[3000], max;
int lis[3000],lmax[3000],rmax[3000]; //lis存序列，l/rmax存各个数最长上升序列
int low,high,mid;
while(scanf("%d",&n) != EOF){
//读数据
for(int i = 0; i < n; i++) scanf("%d",&row[i]);
//二分法查找各数左侧最长上升序列
lis[0] = row[0];
max = lmax[0] = 1;
for(int i = 1; i < n; i++){
low = 0;
high = max;
while(low <= high){
mid = (low + high) / 2;
if(row[i] > lis[max - 1]){ //大于最大值直接插入
lis[max] = row[i]; //插入，更新序列
lmax[i] = max + 1; //更新序列值
max = max + 1;
break;
}
else if(row[i] <= lis[0]){ //小于最小值
lis[0] = row[i];
lmax[i] = 1;
break;
}
else if(row[i] <= lis[mid]){
if(row[i] > lis[mid-1] || max == 1){ //前夹值
lis[mid] = row[i]; //覆盖
lmax[i] = mid + 1;
break;
}else high = mid - 1; //继续判断
}
else if(row[i] > lis[mid]){
if(row[i] < lis[mid+1] || max == 1){ //后夹值
lis[mid + 1] = row[i]; //覆盖
lmax[i] = mid + 2;
break;
}else low = mid + 1;
}
else if(row[i] == lis[mid]){ //同值
lmax[i] = mid + 1; //注意mid是下标从0开始
break;
}
}
}
//二分法查找各数右侧最长上升序列
//倒着来，那我们完全可以把原序列逆转一下
for(int i = 0; i < n / 2; i++){
int tmp = row[i];
row[i] = row[n - i - 1];
row[n - i - 1] = tmp;
}
memset(lis,0,3000); //旧数组归零
lis[0] = row[0];
max = rmax[0] = 1;
for(int i = 1; i < n; i++){
low = 0;
high = max;
while(low <= high){
mid = (low + high) / 2;
if(row[i] > lis[max - 1]){ //大于最大值直接插入
lis[max] = row[i]; //插入，更新序列
rmax[i] = max + 1; //更新序列值
max = max + 1;
break;
}
else if(row[i] <= lis[0]){ //小于最小值
lis[0] = row[i];
rmax[i] = 1;
break;
}
else if(row[i] <= lis[mid]){
if(row[i] > lis[mid-1] || max == 1){ //前夹值
lis[mid] = row[i]; //覆盖
rmax[i] = mid + 1;
break;
}else high = mid - 1; //继续判断
}
else if(row[i] > lis[mid]){
if(row[i] < lis[mid+1] || max == 1){ //后夹值
lis[mid + 1] = row[i]; //覆盖
rmax[i] = mid + 2;
break;
}else low = mid + 1;
}
else if(row[i] == lis[mid]){ //同值
rmax[i] = mid + 1; //注意mid是下标从0开始
break;
}
}
}
for(int i = 0; i < n / 2; i++){
int tmp = rmax[i];
rmax[i] = rmax[n - i - 1];
rmax[n - i - 1] = tmp;
}
//计算最少剔除人数 = n - (lmax[i] + rmax[i] - 1)
max = 0; //其实没必要归0，因为左右相加肯定大
for(int i = 0; i < n; i++){
int tmp =lmax[i] + rmax[i] - 1;
if(max < tmp) max = tmp;
}
printf("%d\n",n - max);
}
return 0;
}
