每日一题C++版(合唱队)

编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程)

特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。

合唱队

题目描述

计算最少出列多少位同学,使得剩下的同学排成合唱队形

说明:

N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。 
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,   则他们的身高满足存在i(1<=i<=K)使得T1Ti+1>......>TK。 
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

输入描述:

整数N

输出描述:

最少需要几位同学出列

示例

输入

8

186 186 150 200160 130 197 200

输出

4

分析

首先计算每个数在最大递增子串中的位置(如何计算后文有讲解)

186 186 150 200 160 130 197 200 quene

1     1     1     2     2     1     3     4 递增计数

然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置

200  197  130  160  200  150 186  186   反向quene

1      1      1      2     3      2     3       3      递减计数

然后将每个数的递增计数和递减计数相加

186  186  150  200  160  130 197  200   quene

1      1      1     2       2     1     3      4       递增计数

3      3      2     3       2     1     1      1       递减计数

4      4      3     5       4     2     4      5       每个数在所在队列的人数+1(自己在递增和递减中被重复计算)

如160这个数

在递增队列中有2个人数

150  160

在递减队列中有2个人数

160  130

那么160所在队列中就有3个人

150  160  130

每个数的所在队列人数表达就是这个意思

总人数 - 该数所在队列人数 = 需要出队的人数

所以本题关键的问题就是如何找出最大的递增序列和递减序列。递减序列可以看作倒叙后的最大递增序列。因此,关键问题就是如何找到最大递增序列。小白采用的方法是首先将每一个数都遍历一次,首先将每个数都记为单独的递增序列,也就是位数为1,之后循环的过程中进行比较,如果后一个数比自己大,则比较后一个数的位数与当前位数+1的大小,如果当前数的位数+1大于后一个数的位数,则将后一个数的位数改为当前数的位数+1,否则不变。如果后面的数比当前数小,则用后一位数与第一层循环的数进行比较,采用同样的方式对位数进行更改。之后以后一位数变成当前数,再次进行比较,直到第一层遍历结束。

代码

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

class Solution
{
public:
 Solution(){}
 vector<int> GetOrder(vector<int> number, int n)
 {
   vector<int> order(n, 1);
   for (int i = 0; i < n; i++)
   {
     int m = number[i];
     int k = i;
     for (int j = i + 1; j < n; j++)
     {
       if (m < number[j] && order[k] >= order[j])
       {
         order[j] = order[k] + 1;
         m = number[j];
         k = j;
       }
       if (number[i]<number[j] && order[i] >= order[j])
       {
         order[j] = order[i] + 1;
         m = number[j];
         k = j;
       }
     }
   }
   return order;
 }
 int Maxorder(vector<int>Inorder, vector<int> Deorder)
 {
   int max;
   vector<int> sum;
   for (int i = 0; i < Inorder.size(); i++)
   {
     sum.push_back(Inorder[i] + Deorder[Inorder.size() - 1 - i]);
   }
   max = sum[0];
   for (int i = 1; i < Inorder.size(); i++)
   {
     if (max < sum[i])
     {
       max = sum[i];
     }
   }
   return max;
 }

private:

};

int main()
{
 int n;
 while(cin >> n)
   {
 vector<int> number;
 vector<int> denumber(n,0);
 Solution solution;
 vector<int> Inorder;
 vector<int> Deorder;
 
 for (int k = 0; k < n; k++)
 {
   int i;
   cin >> i;
   number.push_back(i);
 }
 for (int i = 0; i < n; i++)
 {
   denumber[i] = number[n-1-i];
 }
 Inorder = solution.GetOrder(number, n);
 Deorder = solution.GetOrder(denumber, n);
 int max = solution.Maxorder(Inorder, Deorder);
 cout << n - max + 1 << endl;
   }
 return 0;
}

运行结果

(0)

相关推荐

  • ​LeetCode刷题实战303:区域和检索 - 数组不可变

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战310:最小高度树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • C++ STL 优先队列 (priority_queue)

    std::priority_queue <queue> 优先队列   1.第一个元素始终为最大元素.   2.有着类似于堆的特性,它可以在其中随时插入元素.   3.支持下标访问(随机访问 ...

  • 小尾学长

    Redis 常见面试热点题 摘要:Redis 常见面试热点题 1.什么是Redis? Redis 是完全开源免费的,遵守BSD协议,是一个高性能的key-value数据库. 2.Redis 与其他 k ...

  • 浙大版《数据结构(第2版)》题目集-习题8.2

    习题8.2 银行排队问题之单队列多窗口加VIP服务 (30point(s)) 假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙.当有窗口空闲时,下一位顾客即去该窗口 ...

  • 剑指offer之滑动窗口的最大值

    剑指offer之滑动窗口的最大值

  • 【黑客数学·每日一题】暑假期间“每日一题”汇总版

    各位黑客伙伴们: 大家好!随着暑期的结束,我们迎来了崭新的学期,"每日一题"的发布时间也正式恢复为常规的每周一到周五的下午(一周五期). 有部分黑客伙伴们在暑假安排了各种各样精彩活 ...

  • 每日一题 C++版(走迷宫)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(汽水瓶)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(简单密码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(分类有效的IP地址和掩码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(坐标移动)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(组成最大的数)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(电话号码分身)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(区间合并)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...