Lottery
算法本质
思维
题目大意（略微抽象）
初始存在玩家和另外n个人参加彩票游戏，每个人可以在[0~m]中选择一个数字，随后会公布其中随机的一个数字作为中奖值，最靠近中奖值的k个人会获奖：
- 玩家在同等情况下处于劣势：
当玩家选择3，另一人选择7，中将数字是5时，另一人的中将优先级更高
作为玩家，在公布中奖值前你已经拿到了其他n人选择的数字，做出最优解选择——若多个最优解，选择最小的数字。
输出选择可以覆盖的中奖值数目、选择的数字。
n k <= 1e6
m <= 1e18思路推演
这个复杂度明确告诉我们，以数字为单位思考不可行，必须以人为单位思考，顺其自然的发现，其编号无意义，将其按大小排列后审视。
既然是以人为单位，以样例1为例子1 3 4为例子，一种朴素的想法就是：O(1)计算出[0, 1)的最佳值、O(1)计算出[1, 3)的最佳值……
假设我们选择x值，则尝试计算可以覆盖的中奖值数目，显然那需要是一个区间，思考区间的左右值由什么确定。
对于区间左端点而言，一定是x值恰好为k个最近值的最右边的值。
假设k=3，现在x在v[7]和v[8]之间（不含端点）
左端点其实可以视作x和v[5]的争夺，同理右端点可以视作x和v[10]的争夺，如果x为某个具体的数字的话，可以相对简单的计算出左右端点的值（这里会得到一个简单的公式）。
但是x是处于某个范围的，观察公式可以发现，如果x在范围内移动偶数的距离，右端点-左端点+1的结果会保持不变，考虑题目喜欢最小的值，所以我们可以只考虑x=v[7]+1和x=v[7]+2的情况，当然需要保证x<v[8]。
然后再特殊考虑x=v[i]的情况。
综合来看，写一个函数，可以通过位置求得覆盖个数。
ac核心代码（还没过）
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)