广联达校招-算法-笔经

时间：2020-07-22 15:30

一.编程1
平行四边形构造
时间限制： 3000MS
内存限制： 589824KB题目描述：
给出你n条长度不一的边，请你从中选择四条边，组成一个最大的平行四边形。
请你输出最大的平行四边形的面积。

输入描述
输入第一行包含一个正整数n，表示边的数量。(4<=n<=50000)
输入第二行包含n个正整数，表示n条边的长度，边的长度不会超过10^9。
输出描述
输出仅包含一个正整数，即最大的平行四边形的面积，无解则输出-1。

样例输入
5
3 3 4 4 5
样例输出
12

思路：先排除只有1个的边长，再选最大的和次大的（如果有一个边长有4个，则取一个max即可）

d = {}
n = input()
ls = map(int,input().split())
for i in ls:
    d[i] = d.get(i, 0) + 1
a = []
b = []
for j in d.keys():
    if d[j] >= 2:
        a.append(j)
    if d[j] >= 4:
        b.append(j)

a=sorted(a)
b=sorted(b)
if len(a)>=2:
    if not b :
        print(a[-1]*a[-2])
    else:
        print(max(a[-1]*a[-2],b[-1]*b[-1]))
else:
    print(-1)

二.编程2
排序
时间限制： 3000MS
内存限制： 589824KB题目描述：
有一种排序算法定义如下，该排序算法每次只能把一个元素提到序列的开头，例如2，1，3，4，只需要一次操作把1提到序列起始位置就可以使得原序列从小到大有序。
现在给你个乱序的1-n的排列，请你计算最少需要多少次操作才可以使得原序列从小到大有序。

输入描述
输入第一行包含两个正整数n ，表示序列的长度。(1<=n<=100000)
接下来一行有n个正整数，表示序列中的n个元素，中间用空格隔开。(1<=a_i<=n)
输出描述
输出仅包含一个整数，表示最少的操作次数。

样例输入
4
2 1 3 4
样例输出
1

思路：data为原数组，nums为data的副本，对nums sort,然后以排序后的nums为基准，看data从后往前比较有多少个数是按照nums的顺序排序的，用n-count这个数字就是结果

举个例子 现在有 3 6 1 4 2 5 这个序列 ，那么 6 是不用移动的。

我们先把 5移动到最前，此时变成 5 3 6 1 4 2

再把 4 移动到 最钱 就变成 4 5 3 6 1 2

接着移动 3 到最前就变成 3 4 5 6 1 2

移动2就变成 2 3 4 5 6 1，最后移动 1 变成我们需要的 1 2 3 4 5 6；共需移动5次，结果为5

def sorthigh(array): 
    n=len(array)
    ls=sorted(array)
    count = 0

    j = n-1
    for i in range(n-1,-1,-1):
        if ls[j] == array[i]:
            count+=1
            j-=1

    return n-count

三.编程3
AOE
时间限制： 3000MS
内存限制： 589824KB题目描述：
在一个2D横版游戏中，所有的怪物都是在X轴上的，每个怪物有两个属性X和HP，分别代表怪物的位置和生命值。
玩家控制的角色有一个AOE（范围攻击）技能，玩家每次释放技能可以选择一个位置x，技能会对[x-y,x+y]范围内的所有怪物造成1点伤害，请问，玩家最少需要使用多少次技能，才能杀死所有怪物，怪物血量清0即视为被杀死。

输入描述
输入第一行包含一个两个正整数n和y，分别表示怪物的数量和技能的范围。（1<=n<=100000）
接下来有n行，每行有两个正整数x和hp分别表示一只怪物的位置和血量。(1<=x,hp<=10^9)
输出描述
输出仅包含一个整数，表示最少使用的技能次数。

样例输入
3 5
1 10
10 5
22 3
样例输出
13

思路：贪心，先对怪物从小到大排序，每次从消灭最左的怪物，在[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血。 然后再找下一个血量大于0的怪物，直到消灭所有怪物。

原理：你肯定需要消灭最左的怪物->消灭最左怪物的点肯定在[最左怪物位置，最左怪物位置+y]之间 -> 所以选择[最左怪物的位置，最左怪物位置 + 2 * y]区间的怪物也一起掉血，直到消灭所有怪物

四.单选
线性规划问题与其对偶问题有可行解，下列正确的结论是( )
A.对偶问题有最优解，但线性规划没有
B.线性规划有最优解，但是对偶问题没有
C.线性规划与对偶问题都没有最优解
D.线性规划与其对偶问题有最优解

参答：《最优化理论与算法》（陈宝林，清华大学出版）书上P127 推论2：若互为对偶线性规划问题都有可行解，则都有最优解