总揽

两题都是10行代码不到就写了

第一题

题意

你有一个操作系统，他将要执行n个任务，每个任务有两个阶段，准备阶段和执行阶段，任务必须先完成准备，然后才能执行。

你的操作系统在任意时刻可以执行一个任务，并同时准备多个任务

问你最少花费多少时间可以执行完所有的任务

输入

n表示n个任务

n行，第一个数字为准备时间，第二个数字为执行时间

输入

1
2
3

2
1 5
4 1

输出

1

7

备注

先准备一个时间，然后用5个时间执行第一个任务，然后花一个时间执行第二个任务

题解

按照准备时间从小到大排序，然后依次模拟即可

第二题

描述

给你长度为n个数组（都是正数），你可以花费1的代价来改变一个数的值（改成正数），然后给你一个x，现在你需要用最小的代价把这个数组变长公差为x的等差数列，输出最小的代价。

输入

1
2

5 3
1 3 1 3 5

输出

1

3

备注

改成1 3 5 7 9

问题转化

把数组的下标当作横坐标，把数组的值当作纵坐标，你可以得到二维平面内的n个点。

等差数列的点都在一条直线上，斜率就是公差，首项就是y轴截距

现在问题转化为，给你二维平面内的n个点，找到一条斜率为x点直线经过尽可能多的点，且y轴截距大于0，输出没有经过的点点个数。

问题解决

由于截距为x，我们枚举每个点所在的直线，计算出y=kx+b, 我们对直线进行hash, 由于斜率相同，我们只需要对截距hash，不妨设直线的hash值就是截距的大小

我们对hash值记数，出现次数最多的且hash值大于0的那个条直线，就是我们的答案找到的直线，不妨设这个直线的hash值出现了m次，最终答案就是n-m.