小明特别喜欢听歌他经常在qq音乐上寻找歌曲并加入他的歌单。但是小明有强迫症他希望他的歌单里的歌的时长是非递减的所以当小明往歌单里加歌时他会从后往前删除时长比新歌长的歌直到歌单继续保持歌的时长非递减；也就是说假设小明歌单里有三首歌时长分别为10，20、30_此时小明新加入了一首时长为15的歌他就会把时长为20以及30的歌删掉现在的歌单就变只剩下了10，15两首歌如果再来一首时长为30的歌可以直接加入歌单（10 15 30）。假设当前小明的歌单是空的，他有n首歌要依次加入问最后小明的歌单能有多少首歌呢？
基于new bing的实现：
这道题其实可以使用贪心算法求解。具体来说，我们可以维护一个数组 a，表示当前小明的歌单。接下来，对于每首要添加的歌，我们都将它插入到合适的位置，即尽量保证时长非递减。如果在插入某首歌之后发现时长不再是非递减的，那么就从歌单末尾开始删除时长比新歌长的歌曲直到时长为止。
以下是这个算法的 C 语言实现：
#include <stdio.h>
#define MAX_N 100000
// 维护歌单的数组
int a[MAX_N];
// 当前歌单中歌曲的数量
int n = 0;
// 将 x 插入到数组 a 的合适位置
// 使得 a[i] <= x <= a[i+1]
void insert(int x) {
int i;
// 从后往前扫描数组 a，找到第一个 a[i] <= x 的位置
for (i = n - 1; i >= 0; i--) {
if (a[i] <= x) {
break;
}
}
// 将 x 插入到 a[i+1] 的位置
a[i+1] = x;
n = i + 2;
// 从后往前删除时长比新歌长的歌曲直到时长为止
for (int j = n - 1; j >= 0 && a[j-1] > a[j]; j--) {
a[j-1] = a[j];
n--;
}
}
int main() {
int m, x;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%d", &x);
insert(x);
}
printf("%d\n", n);
return 0;
}
在主函数中，我们首先读入小明要添加的歌曲数 m，然后依次读入每首歌的时长，并将它们插入到歌单数组 a 中。最后，输出当前歌单的长度 n。
需要注意的是，在本算法中我们使用了一个类似双指针的方法，从后往前扫描歌单数组 a，找到第一个时长不超过新歌的位置，然后将新歌插入到该位置，从而保证时长非递减。此外，为了维护时长非递减，我们还需要在每次插入新歌之后检查并删除时长比新歌长的歌曲直到时长为止。
供参考：
#include<stdlib.h>
#include<stdio.h>
# define Maxsize 100
# define ElemType int
# define Status int
//结构
typedef struct {
ElemType* elem;
int length;
int listsize;
}SqList;
//初始化
Status InitList(SqList& L)
{
L.elem = (ElemType*)malloc(Maxsize * sizeof(ElemType));
if (!L.elem) return 0;
L.length = 0;
L.listsize = Maxsize;
return 1;
}
//输入数据
Status Enter(SqList& L, int n)
{
int i;
for (i = 0; i < n; i++)
{
scanf("%d", &L.elem[i]);
L.length++;
}
return 1;
}
//输出数据
Status Out(SqList& L)
{
int i;
if (!L.elem)
return 0;
for (i = 0; i < L.length; i++)
printf("%d ", L.elem[i]);
printf("\n");
return 1;
}
//加入新歌
Status Handle(SqList& L,int x)
{
int i, j;
for (i = 0, j = 0; i < L.length; i++)
{
if (L.elem[i] < x)
L.elem[j++] = L.elem[i];
}
L.elem[j++] = x;
L.length = j;
return 1;
}
int main()
{
SqList L;
InitList(L);
int n, x;
printf("输入原始数据的规模：");
scanf("%d", &n);
printf("输入原始数据：");
Enter(L, n);
printf("原始的数据：");
Out(L);
while (printf("输入新歌的时长:"), scanf("%d", &x) == 1 && x != -1) Handle(L, x); // -1 时结束输入
printf("最终的数据：");
Out(L);
printf("最后的歌单有 %d 首歌。", L.length);
return 0;
}
针对你的问题结合chatgpt知识库请参考以下内容：
这是一个典型的贪心算法问题。
首先，我们需要明确一个结论，即如果一首歌曲要加入歌单时，它的时长不小于已有歌曲的最大时长，那么这首歌曲可以直接添加到歌单末尾，否则需要删除歌单中比这首歌曲时间长的歌曲，从后往前删除元素直到满足要求。
那么具体操作应该怎样进行呢？我们可以使用一个数组 $a$ 来存储小明当前的歌单，用变量 $last$ 记录当前歌单中最大时间值，初始值为 $0$。当加入一首新的歌曲时，我们按照上述结论进行以下操作：
最终，小明的歌单长度即为数组 $a$ 的长度。
以下是 Python 代码实现：
def playlist(n, songs):
res = []
last = 0
for i in range(n):
if songs[i] >= last:
res.append(songs[i])
last = songs[i]
else:
idx = len(res) - 1
while idx >= 0 and res[idx] > songs[i]:
idx -= 1
res[idx+1:] = [songs[i]]
last = songs[i]
return len(res)
n = int(input())
songs = []
for i in range(n):
songs.append(int(input()))
print(playlist(n, songs))
时间复杂度为 $O(n)$。
如果你想进一步优化时间复杂度，可以使用二分查找来寻找需要删除的歌曲的位置。具体步骤如下：
以下是优化后的 Python 代码实现：
import bisect
def playlist(n, songs):
res = []
last = 0
for i in range(n):
if songs[i] >= last:
res.append(songs[i])
last = songs[i]
else:
pos = bisect.bisect_left(res, songs[i])
res[pos:] = [songs[i]]
last = songs[i]
return len(res)
n = int(input())
songs = []
for i in range(n):
songs.append(int(input()))
print(playlist(n, songs))
使用二分查找后的时间复杂度为 $O(n\log n)$。