敖屹

用户名：uq_67615411132

访问量：357

签　名：

啥都学，但是啥都学不会

等　　级
排　　名	2463
经　　验	2202
参赛次数	7
文章发表	2
年　　龄	19
在职情况	学生
学　　校	长江大学文理学院
专　　业	计算机应用技术

　　自我简介：

一个喜欢数学和计算机的小菜鸡

TA的其他文章

拦截导弹(C++和Java)(动态规划模板：最长上升子序列)
浏览：154

你可能喜欢

数列极差题解（C++和Java）（超级详细，带有贪心策略的证明）

　　作者: 敖屹　　　　发表时间：2023-11-22 17:28:59 浏览：130　|　评论：0　

原题链接：信息学奥赛一本通T1427-数列极差

# 数列极差题解（C++和Java）（超级详细，带有贪心策略的证明）
**时间复杂度:O(NlogN)
思路:类似哈夫曼树的操作**
##贪心思路:
从数量小的时候入手
假如有3个数a,b,c,并且假设$$a< b< c$$
那么会有三种情况
$$num1=(ab+1)c+1=abc+c+1$$
$$num2=(ac+1)b+1=abc+b+1$$
$$num3=(bc+1)a+1=abc+a+1$$
则有$$num1>num2>num3$$
**则可以猜测:**
1.优先取出数组中第一大的值和第二大的值,将他们进行a*b+1操作,再插入回去,以此类推,最终得到的结果最小
2.优先取出数组中第一小的值和第二小的值,将他们进行a*b+1操作,再插入回去,以此类推,最终得到的结果最大
**这里猜测的证明放到最后去证明,这里先说一下假如这个猜测成立,如何去实现**
###贪心实现的步骤:
**拆分成小问题:**在数组中取出两个数，进行a*b+1操作之后使得结果(最大/最小)
小问题的实现:取出数组中第一(大/小)的值和第二(大/小)的值,将他们进行a*b+1操作

**小问题合成大问题:**
1.取出数组中第一(大/小)的值和第二(大/小)的值
2.将他们进行a*b+1操作之后将a*b+1的值插入进去,并第一(大/小)的值和第二(大/小)的值删除
3.继续1、2步骤进行,直到数组只剩一个元素的时候,得出最小值/最大值(注意结论是反过来的)
###具体代码实现方式:
1. 先建立大根堆和小根堆,并且将数组中的值全都插入进去
2. 大根堆:定义两个变量a.b。
		用a接收第一大的数,然后弹出
		用b接收第二大的数,然后弹出
		将a*b+1的值插入到堆中
		如上过程循环执行,直到堆中只 剩下1个元素的时候,退出循环、

3.小根堆和大根堆同理
4.剩下大根堆/小根堆的堆顶就是对应的min和max了
5.最后让(小根堆的堆顶 - 大根堆的堆顶)就是答案了

##算法时间复杂度的分析：
1.每次操作会弹出$$2$$个数再插入回去$$1$$个数,直到堆只剩$$1$$个数的时候,此过程一共需要$$N-1$$次操作
2.弹出$$2$$个数$$2logN$$次运算,插入$$1$$个数$$logN$$次运算,访问栈顶$$2$$次运算,所以每次操作需要$$3logN+2$$次运算
3.则处理小根堆需要$$(N-1)(3logN+2)$$次运算,大根堆同理
4.则总共需要$$2(N-1)(3logN+2)=6NlogN+4N-6logN-4$$次运算
5.则算法时间复杂度为$$O(NlogN)$$

##贪心策略的证明：
###两个猜测
1.优先取出数组中第一大的值和第二大的值,将他们进行$$ab+1$$操作,再插入回去,以此类推,最终得到的结果最小
2.优先取出数组中第一小的值和第二小的值,将他们进行$$ab+1$$操作,再插入回去,以此类推,最终得到的结果最大
###将猜测进行证明:
由于猜测$$1$$和猜测$$2$$互为逆否命题,所以只要证明猜测1,猜测2就一定是对的，
**猜测1的证明:**
**由于上面证明了3个数的情况,那么将3个数的情况扩展成n个数的情况就好了**
####3个数的情况：
假如有3个数$$a,b,c$$,并且假设$$a>b>c$$
那么会有三种情况
$$num1=(ab+1)c+1=abc+c+1$$
$$num2=(ac+1)b+1=abc+b+1$$
$$num3=(bc+1)a+1=abc+a+1$$
由于$$c<b<a$$
则有$$num1<num2<num3$$
####4个数的情况：
假如有4个数$$a,b,c,d$$,并且假设$$a>b>c>d$$
那么可以分成四种情况
$$num1=(abc+c+1)d+1=abcd+cd+d+1$$
$$num2=(abd+d+1)c+1=abcd+cd+c+1$$
$$num3=(acd+d+1)b+1=abcd+bd+b+1$$
$$num4=(bcd+d+1)a+1=abcd+ad+a+1$$
由于$$d<c<b<a$$,且在$$a,b,c,d$$四个数中选2个相乘,最小的是$$c*d$$
则$$num1<num2<num3<num4$$
####扩展到n个数的情况：
假如有$$n$$个数$$a[1],a[2],a[3],...,a[n-1],a[n]$$,并且假设对任意$$0<i<n$$,都有$$a[i]>a[i+1]$$
由于有如上假设,显然有如下规律：
在$$a[1],[2],a[3],...,a[n]$$这$$n$$个数中选$$i$$个数相乘,最小的是$$\prod_{k=n-i}^{n}a[k]$$
```math 
那么可以分成n种情况,由如上规律可以知道所有情况中最小的是\\
num=\prod_{i=1}^{n}a[i]+\sum_{i=3}^{n} (\prod_{k=i}^{n}a[k])+1
```
很明显，如上情况的式子就是先取出数组中第一大的值和第二大的值,将他们进行a*b+1操作,再插入回去依此操作到数组只剩下一个元素时的值。则此贪心策略证明完毕

##关于C++的stl中堆的一些介绍：
**由于我这里有C++的实现，为了方便阅读，这里说一下C++的STL中有关于堆的一些函数**
```
q.push(T num);	  //在堆中插入一个数
q.pop();			//在堆中弹出(最大/最小)的数(这里弹出最大还是最小取决于你建立的是大根堆还是小根堆)
q.top();			//取堆头(也就是最大/最小值)
q.size();		   //返回堆中元素的数量
```
##具体代码实现(C++的实现)(Java的实现在后面)
```
#include <iostream>
#include <queue>

using namespace std;

int main() {
	priority_queue<int, vector<int>, greater<int> > minQ;	//建立小根堆
	priority_queue<int, vector<int>, less<int> > maxQ;		//建立大根堆
	int n,num;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		minQ.push(num);
		maxQ.push(num);
	}
	int a, b;
	while (minQ.size() > 1) {
		a = minQ.top();
		minQ.pop();
		b = minQ.top();
		minQ.pop();
		minQ.push(a * b + 1);
	}
	while (maxQ.size() > 1) {
		a = maxQ.top();
		maxQ.pop();
		b = maxQ.top();
		maxQ.pop();
		maxQ.push(a * b + 1);
	}
	cout << minQ.top() - maxQ.top() << endl;
	return 0;
}
```
##具体代码实现(Java的实现)
```
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //小根堆
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        //大根堆
        PriorityQueue<Integer> maxQ = new PriorityQueue<Integer>((o1,o2) -> o2 - o1);
        int n = scanner.nextInt();
        int num;
        for (int i = 0; i < n; i++) {
            num = scanner.nextInt();
            minQ.add(num);
            maxQ.add(num);
        }
        int a,b;
        while(minQ.size() > 1){
            a = minQ.poll();
            b = minQ.poll();
            minQ.add(a*b+1);
        }
        while(maxQ.size() > 1){
            a = maxQ.poll();
            b = maxQ.poll();
            maxQ.add(a*b+1);
        }
        System.out.println(minQ.peek() - maxQ.peek());
        scanner.close();
    }
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

敖屹

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

点我有惊喜！你懂得！

校门外的树（C语言代码）

数列极差题解（C++和Java）（超级详细，带有贪心策略的证明）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

买不到的数目（C++代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-判定字符位置（C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-自由落体问题（C语言代码）

1113题解

敖屹

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

点我有惊喜！你懂得！

校门外的树 （C语言代码）

数列极差题解（C++和Java）（超级详细，带有贪心策略的证明）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

买不到的数目 （C++代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-判定字符位置 （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

1113题解

蛇行矩阵（C语言代码）

校门外的树（C语言代码）

　　评论区

买不到的数目（C++代码）

C语言考试练习题_排列（C语言代码）

WU-判定字符位置（C++代码）

C语言训练-自由落体问题（C语言代码）