关键词：
problem
随机题意 Accepts: 1411 Submissions: 3641
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
给一个整数数组 a_1,a_2,\\cdots,a_na
1
,a
2
,⋯,a
n
和 kk ，你想要找到一个最大的值 xx ，使得存在另一个整数数组 b_1,b_2,\\cdots, b_nb
1
,b
2
,⋯,b
n
满足 |a_i-b_i|\\leq k(1\\leq i\\leq n)∣a
i
−b
i
∣≤k(1≤i≤n) 且 b_nb
n
中共有 xx 个不同的数。
Input
第一行一个正整数 T(1\\leq T\\leq 10)T(1≤T≤10) ，代表测试组数。
接下来 TT 组数据中，每组数据的第一行包含包含两个整数 n,k(1\\leq n\\leq 100000,0\\leq k\\leq 10^9)n,k(1≤n≤100000,0≤k≤10
9
) 。
第二行包含 nn 个整数 a_1,a_2,\\cdots,a_n(1\\leq a_i\\leq 10^9)a
1
,a
2
,⋯,a
n
(1≤a
i
≤10
9
) 。
Output
TT 行，每行一个整数 xx ，代表每组数据的答案。
Sample Input
1
6 1
1 2 2 2 2 3
Sample Output
Copy
5
solution
- 考虑到ai-k<=bi<=ai+k，可以将n个输入的ai转换为n个区间，原题目转换为在n个区间中选尽可能多的区间。
- 可以贪心的按照左端点从小到大排序，然后从左往右选。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int maxn = 1e5+10;
struct nodeLL l, r;a[maxn];
bool cmp(node x, node y)return x.l!=y.l?x.l<y.l:x.r<y.r;
int main()
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin>>T;
while(T--)
LL n, k; cin>>n>>k;
for(int i = 1; i <= n; i++)
LL x; cin>>x;
a[i] = (node)x-k,x+k;
sort(a+1,a+n+1,cmp);
//for(int i = 1; i <= n; i++)
// cout<<a[i].l<<" "<<a[i].r<<"\\n";
LL t = a[1].l, cnt = 1;//t表示上一次选的位置
for(int i = 2; i <= n; i++)
if(a[i].l>t)
cnt++;
t = a[i].l;
else if(a[i].r>t)
cnt++;
t = t+1;
cout<<cnt<<"\\n";
return 0;
/*
ai-k<=bi<=ai+k
*/
2021年百度之星·程序设计大赛-初赛二1005水题（贪心结论）(代码片段)
problemsolution开始还以为是CF987E，但是奇偶性并不一样，，结果是个贪心乱搞。。样例都没过交了能过，醉了。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;intmain() ios::sync_with_stdio(0),ci 查看详情
2021年百度之星·程序设计大赛-初赛二1001签到（找规律，快速幂）(代码片段)
problem签到Accepts:6141Submissions:13643TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给a,ba,b，每次a,ba,b会变为a+b,a-ba+b,a−b，问kk次之后变成了哪两个数 查看详情
2021年百度之星·程序设计大赛-初赛二1003魔怔（并查集，联通性，欧拉回路）(代码片段)
problemsolution发现除了起点和终点，剩下所有点周围的边都会被恰经过偶数次，所以这些点初始连向了偶数条白边。考虑由白边连接形成的图，每个连通块中度数为奇数的点一定为偶数个。所以起点所在连通块最多有两... 查看详情
2021年百度之星·程序设计大赛-复赛1002addormultiply1（第2类斯特林数）(代码片段)
problemsolution想到了是n个小球放到m个盒子里以后，剩下的就是板子了#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintmaxn=3010;constintmod=1e9+7;LLfac[maxn];LLinit()fac[0]= 查看详情
2020百度之星程序设计大赛初赛二(代码片段)
A.Poker(Hdu????)题目大意给定n个币，每次投至少m个，当投(x)个时，给回(lfloorx imes(1-p\%)floor)。问你最多能投多少次。解题思路很显然每次投(m)元是最优的，因为但凡投(m+1)元，给回的钱数不可能会增加二，要不不变要不减少。每次... 查看详情
2017"百度之星"程序设计大赛-初赛（a）
2017"百度之星"程序设计大赛-初赛（A）hdu6108 求出n-1的因子个数即可#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#definerep(i,a,b)for(inti=a;i<=b;++i)#de 查看详情
2014年百度之星程序设计大赛-资格赛1002diskschedule（双调欧几里得旅行商问题）
ProblemDescription有非常多从磁盘读取数据的需求。包含顺序读取、随机读取。为了提高效率，须要人为安排磁盘读取。然而，在现实中。这样的做法非常复杂。我们考虑一个相对简单的场景。磁盘有很多轨道，每一个轨道有很多扇... 查看详情
2018“百度之星”程序设计大赛-初赛（b）(代码片段)
degree Accepts:1581 Submissions:3494 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:131072/131072K(Java/Others)ProblemDescription度度熊最近似乎在研究图论。给定一个有 NN 个 查看详情
2018“百度之星”程序设计大赛-初赛（b）(代码片段)
rank264，三题水过~hdu6380_degree#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=200005;intin[maxn];intn,m,k;intmain()intt;scanf("%d",&t);while(t--)memset(in,0,sizeof(in) 查看详情
hdu6122今夕何夕数学公式（2017"百度之星"程序设计大赛-初赛（a））
今夕何夕TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1295 AcceptedSubmission(s):455ProblemDescription今天是2017年8月6 查看详情
2018“百度之星”程序设计大赛-初赛（a）(代码片段)
度度熊拼三角 Accepts:2536 Submissions:4433 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)ProblemDescription度度熊有 NN 根木棒，每根木棒的长度为a_ia? 查看详情
hdu5253连接的管道(kruskal)(百度之星程序设计大赛-初赛)
连接的管道TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1323 AcceptedSubmission(s):519ProblemDescription老Jack有一片农田 查看详情
2021百度之星初赛第二场1002.随机题意(贪心)(代码片段)
LINK对于aia_iai,满足条件的bib_ibi落在区间[ai−k,ai+k][a_i-k,a_i+k][ai−k,ai+k]中考虑对这些区间按左端点排序,问题转化为让最多的区间分配到点(一个点只能属于一个区间)考虑左端点最小的区间范围是[li,ri][l_i,r_i][li,... 查看详情
2018“百度之星”程序设计大赛-初赛（a）(代码片段)
第二题还算手稳+手快？最后勉强挤进前五百（期间看着自己从两百多掉到494名）1001 度度熊拼三角 （hdoj6374）链接：http://acm.hdu.edu.cn/showproblem.php?pid=6374签到题 题意：给n根木棒求可以拼出的周长最长的三角形可以... 查看详情
[singularity]百度之星程序设计大赛初赛1001小c的倍数问题
小C的倍数问题 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的... 查看详情
2017"百度之星"程序设计大赛-初赛（a）01，05，06
小C的倍数问题 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一... 查看详情
hdu6114chess组合数（2017"百度之星"程序设计大赛-初赛（b））
ChessTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):513 AcceptedSubmission(s):319ProblemDescription車是中国象棋中的一种棋 查看详情
2017"百度之星"程序设计大赛-初赛（a）
小C的倍数问题ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P... 查看详情