三道C++题目,Problem 1 分队问题(team.cpp/c/pas)【题目描述】给定 n 个选手,将他们分成若干

三道C++题目,
Problem 1 分队问题(team.cpp/c/pas)
【题目描述】
给定 n 个选手,将他们分成若干只队伍.其中第 i 个选手要求自己所属的队
伍的人数大等于 a[i]人.
在满足所有选手的要求的前提下,最大化队伍的总数.
注：每个选手属于且仅属于一支队伍.
【输入格式】
第一行一个整数 n,表示人数.
以下 n 行,每行一个整数表示 a[i].
【输出格式】
输出队伍总数的最大值.数据保证有解.
Problem 2 数字对(numpair.cpp/c/pas)
【题目描述】
对于一个数字对(a,b),我们可以通过一次操作将其变为新数字对(a+b,b)
或(a,a+b).
给定一正整数 n,问最少需要多少次操作可将数字对(1,1)变为一个数字对,
该数字对至少有一个数字为 n.
【输入格式】
第一行一个正整数 n
【输出格式】
一个整数表示答案.
Problem 3 压缩函数(compress.cpp/c/pas)
【题目描述】
定义一个对 01 串的压缩函数 f：
f(空串) = 空串.
f(s) = s.其中 s 是一个 01 串.
f(s1,s2) = t,t 是最短的满足 s1 是 t 的前缀且 s2 是 t 的后缀的 01 串.
如 f(001,011) = 0011,f(111,011) = 111011.
f(a1,a2,…,an) = f( f(a1,a2,…,a[n-1]),an)
如 f(000,000,111) = f( f(000,000),111) = f(000,111) = 000111
对于给定的 n 个长度相等的 01 串 a[1],a[2],…,a[n],将其分为两个子
序列 b[1],b[2],…,b[k]和 c[1],c[2],… ,c[n-k],使得
|f(b[1],b[2],… b[k])| + |f(c[1],c[2],… c[n-k])|最小化.
不允许改变 n 个串之间的相对顺序,每个串属于且仅属于一个子序列,允许
某个子序列为空.
注：|s|表示 01 串 s 的串长度.
【输入格式】
第一行一个整数 n,表示 01 串的个数.
以下 n 行,每行 m 个 0 或 1.第 i+1 行表示 a[i].
【输出格式】
输出一个整数 m,表示|f(b[1],b[2],… b[k])| + |f(c[1],c[2],…
c[n-k])|的最小值.
【样例输入 1】
3
01
10
01
【样例输出 1】
4
【样例输入 2】
4
000
111
5 / 5
110
001
【样例输出 2】
8
【样例解释】
样例一：另一个子序列为空,则|f(01,10,01)| = |0101| = 4；
样例二：b = {000,001},c = {111,110},|f(000,001)| + |f(111,110)|
=|0001| + |1110| = 8;
【数据范围】
对于 20%的数据,1

// 第一题

#include <iostream>
#include <algorithm>
using namespace std;

int n, num[100000], dp[100000], dpmax[100000];

int main() {
\x09int maxindex;
\x09ios::sync_with_stdio(false);
\x09cin >> n;
\x09for (int i = 1; i <= n; i++) {
\x09\x09cin >> num[i];
\x09}
\x09sort(num, num + n);
\x09dp[0] = 0;
\x09dpmax[0] = 0;
\x09for (int i = 1; i <= n; i++) {
\x09\x09dp[i] = -1;
\x09\x09maxindex = i - num[i];
\x09\x09if (maxindex < 0) {
\x09\x09\x09dpmax[i] = dpmax[i - 1];
\x09\x09\x09continue;
\x09\x09}
\x09\x09else if (maxindex > i - 1) {
\x09\x09\x09maxindex = i - 1;
\x09\x09}
\x09\x09dp[i] = dpmax[maxindex] + 1;
\x09\x09dpmax[i] = max(dpmax[i - 1], dp[i]);
\x09}
\x09cout << dp[n] << endl;
}