NC216129. 编故事
描述
SMU的校赛又要开始了，HL却为出题犯愁，为什么呢？因为题目要套在一个故事里，至少HL是这么想的，因为他觉得这样题目才显得有逼格，嘻嘻，可是HL并不善于编故事。最后，他想破脑袋，于是遍了这样一个故事：
很久很久以前，有一个古老的王国，这个王国里有n户人家，国王是个很喜欢团结的人，他总是喜欢让他的子民们举行一些活动，来使他们促进团结。这天，他在巡视国家时，发现街上的人走路迈出的步子大小可能不一样。他灵感一现，想到了一个非常有意思且能促进团结的游戏，“两人三足”！！！但是国王喜欢团结，所以他并不想让他的子民分组决出胜负，而是要求每家每户都派出一个人，然后让所有人排成一排，组成一个“m人m+1足”。只要他们能顺利走完一定的路程，国王就会很高兴，然后就会开国库，发粮食！子民很当然很想得到粮食啊，但是他们陷入了困惑，因为每个人的迈出的步子大小是固定的，没法缩小或增大，而且只要有两个人的步子大小差值超过k，那么他们就会集体摔倒，游戏失败。现在他们求助于你，把每家每户的人的步子大小告诉你，让你帮他们确认他们是否可能完成游戏。为什么求助于你呢？因为在这个故事里，你就是他们国家隔壁山上正在修炼的程序员！（滑稽）
两人三足的游戏规则：由两个人团结协作，两人并排站立，一人左腿与另一人右腿的膝盖以下，脚踝以上部分用绳子绑上 比赛在起点处开始出发，至对面标志处折回，返回至起点处，再将绳子解后，交给下一组队员进行比赛，最后以完成时间长短进行排名。
——复制自百度百科
输入描述
第一行两个整数n和k，n(1 <= n <= 100000),表示王国有多少户人家，k(1 <= k <= 1000000000)，表示最大步子和步子差值超过k就会集体摔倒；接下来n行，每行5个整数a(1 <= a <= 1000000000)，第i个整数代表这户人家第i个人步子的大小。
输出描述
输出包含一行，若子民们能完成游戏，输出所有可行方案中的最大步子和最小步子的差值的最小值；若不可能完成游戏，输出-1。
示例1
输入:
4 2 1 2 3 4 5 3 4 6 3 4 3 4 5 6 7 7 1 8 6 11
输出:
1
示例2
输入:
3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
输出:
-1
C++(clang++11) 解法, 执行用时: 215ms, 内存消耗: 4580K, 提交时间: 2021-01-01 18:59:31
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,x,cnt,ans=1e9+7,l=1,num,b[100010];
struct p{
int a;
int id;
}a[500010];
bool cmp(p x,p y){
return x.a<y.a;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=5;j++){
cin>>x;
cnt++;
a[cnt].a=x;
a[cnt].id=i;
}
sort(a+1,a+1+cnt,cmp);
for(int i=1;i<=cnt;i++){
b[a[i].id]++;
if(b[a[i].id]==1) num++;
while(num==n){
ans=min(a[i].a-a[l].a,ans);
b[a[l].id]--;
if(!b[a[l].id]) num--;
l++;
}
}
if(ans>k) cout<<"-1";
else cout<<ans;
return 0;
}