甘肃兰州旅游必去十大景点_营销思路和创新点_网页设计作品_杭州百度seo代理

题目描述

某媒体处理服务负责接收来自多个媒体发送源的媒体包，并根据收到的媒体包进行媒体渲染处理。现在需要计算发送这些媒体包的最少发送源个数。

约束条件如下：

1. 任意媒体包序列号seqs[i]满足：0 ≤ seqs[i] ≤ 65535。
2. 同一个发送源发送的媒体包序列号不会重复，且每次加1（不考虑回绕问题，65535是发送源发送的最后一个媒体包序列号）。如果收到的媒体包序列号不满足该规则，说明这些媒体包必然来自多个发送源。
3. 输入的序列号列表长度范围为1 ≤ seqs.length ≤ 10^5。

输入描述

1. 第一行：一个整数n，表示媒体包序列号列表的长度。
2. 第二行：n个整数，表示媒体包的序列号，序列号之间用空格隔开。

输出描述

输出一个整数，表示最少的媒体包发送源个数。

用例输入

11
1 2 3 4 5 6 7 8 9 10 10

2

媒体包发送源1：1 2 3 4 5 6 7 8 9 10
媒体包发送源2：10
媒体发送源个数为2，因此输出2。

5
65535 0 1 2 3

2

媒体包发送源1：65535
媒体包发送源2：0 1 2 3
媒体发送源个数为2，因此输出2。

解题思路

1. 问题建模：

   • 该问题可以看作是一个计数问题，目标是计算最少的发送源个数。
   • 每个发送源的序列号是连续的，因此可以通过检查序列号的连续性来判断是否来自同一个发送源。

2. 动态规划：

   • 使用一个数组dp记录以每个序列号结尾的发送源数量。
   • 对于每个序列号t：
     • 如果t-1存在且dp[t-1] > 0，则可以将t与t-1合并为同一个发送源。
     • 否则，t必须是一个新的发送源。
   • 最终，dp数组中所有非零值的总和即为最少的发送源个数。

3. 优化：

   • 使用一个固定大小的数组（maxsize = 65536）来存储dp值，避免动态分配。
   • 遍历输入的序列号列表，更新dp数组。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int maxsize = 65536;vector<int> dp(maxsize, 0); // 以i为结尾的发送源数量int n;cin >> n;for (int i = 0; i < n; i++) {int t;cin >> t;if (t > 0 && dp[t - 1]) { // 检查是否可以转移dp[t - 1]--;}dp[t]++; // 无论是否转移，都要加上以本次结尾的发送源}int res = 0;for (int i = 0; i < maxsize; i++) {res += dp[i];}cout << res;return 0;
}