本文主要是介绍Birthday present，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Birthday present
题目描述
Bob’s father’s birthday is coming,.Because Bob’s father is a math teacher so that Bob wanted to give him an array of positive intergers a of length n as a gift.His father thinks that an array’s beauty is the greatest common divisor of all its elements. Bob wants to give him as beautiful an array as possible. But the shop has only one array a left. So Bob wants to decrease some numbers in the array(no more than K for each number).Bob can obtain array b from array a if the following conditions hold: bi > 0; 0 ≤ ai - bi ≤ k for all 1 ≤ i ≤ n.Help Bob find the maximum possible beauty of the array he will give to his father .
输入
The first line contains two integers n and k (1 ≤ n ≤ 3·1e5; 1 ≤ k ≤ 1e6). The second line contains n integers ai (1 ≤ ai ≤ 1e6) — array a.
输出
In the single line print a single number — the maximum possible beauty of the resulting array.
样例输入
6 1
3 6 10 12 13 16
样例输出
3
题目大意：Bob's的父亲生日快到了，他想送给他父亲一个数组长度为n的正整数（送数组？？？），他父亲认为数组的美是这个数组的最大公约数，Bob's想送一个最大公约数最大的数组，但是店里只剩下一个数组了，Bob's可以减少数组中的某些数来改变这个数组的最大公约数，减少最多不超过k。
分析：这个数组的最大公约数<=最小值，并且最小是1；那么我们就可以先找到数组的最小值然后用这个最小值挨个和其他数比较如果全都满足 a[i]-a[i]/min*min<=k&&a[i]-a[i]/min*min>=0 (a[i]/min的余数<=k&&a[i]/min的余数>=0)那么我们要找的就是这个min，否则min自减在循环一次，直到min==1；
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;int main()
{ int n,k;while(scanf("%d%d",&n,&k)!=EOF){int a[300005]={0};int minn=1000005; for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i]<minn)minn=a[i];}int flag,t;for(t=minn;t>0;t--){flag=1;for(int i=0;i<n;i++){if((a[i]-a[i]/t*t>k)||(a[i]-a[i]/t*t<0)){flag=0;break; }}if(flag){printf("%d\n",t);break;}}}return 0;
}这篇关于Birthday present的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
