Problem 1E. 最小化网络并发线程分配
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 1E. 最小化网络并发线程分配
时间限制:1s
空间限制:64MB
题目背景
在网络通信中,存在多种并发网络任务,如资源请求和文件上传。这些任务的执行方式有些是线性或队列式的,而更多是并发执行的,需要服务器进行统一调度。对于多并发网络任务,可以通过多线程处理来提高处理速度。然而,计算资源和网络线程数都是有限的,因此需要找到一种方式来最小化分配给某项并发任务的线程数量。
题目描述
假设有 \(n\)个网络并发任务需要同时开始执行,每个任务都一个权重值,已知一个整数数组\(weights\)表示每个任务的权重值。
你可以为每个网络任务分配一个 整数数字,用来表示分配的网络线程数,且每个任务至少分配\(1\)个网络线程。
由于某种限制,要求 相邻 的两个任务的权值,权重更高的任务必须分配更多的线程(而对于相同权值两个的相邻任务,线程数没有限制)。
请你计算并输出一个整数,表示最小网络并发线程的分配数量。
输入格式
第一行一个整数 \(n\),第二行是一个长度为\(n\)的整数数字\(weights\)
输出格式
一个整数,表示最小网络并发线程的分配数量,这种方式下,所有任务的线程之和最小。
样例输入1
3
1 0 2
样例输出1
5
样例1解释
最小化分配方式为:2 1 2
样例输入 2
6
1 2 2 2 2 1
样例输出 2
8
样例2解释
由于相同权重的线程分配并没有限制,最小化分配方式为:1 2 1 1 2 1
数据范围及限制
对于 \(100\%\) 的数据,\(1\le n\le 5\times10^4,weights[i]\in[1,100]\)