1939-一颗姜会长多高-binary search

 1   

  /*第一行输入两个整数 n,m (1≤n,m≤10^5)，表示姜的个数以及询问次数。
 2 第二行输入 n 个整数 a1,a2,…,an (1≤ai≤10^9)，表示 n 颗姜的初始高度。
 3 接下来输入 m 行，每行两个整数 xi,yi (0≤xi≤10^18,0≤yi*/
 4 #include
 5 #include
 6 int n, m;/*全局定义n,m*/
 7 long long Data[100005];/*全局定义姜的初始高度*/
 8 long long find[100005] = { 0 };/*全局定义寻找数组*/
 9 /*定义两种魔法次数*/
10 long long x[100005];/*单位魔法*/
11 int y[100005];/*无穷魔法*/
12 /*定义快速排序函数*/
13 int cmp(const void* a, const void* b)
14 {
15  return *(int*)a - *(int*)b;
16 }
17 /*定义寻找输出结果函数*/
18 long long Result(long long x, int y)
19 {
20  /*二分法查找*/
21  long long low, high, mid;
22  long long Flow, Fhigh, Fmid, Fmid1;
23  long long result;/*定义输出值*/
24  low = y, high = n - 1;
25  if (y == n - 1)
26  {
27   result = Data[n - 1] + x;
28  }
29  else
30  {
31   for (; low <= high;)/*构造循环寻找*/
32   {
33    mid = (low + high) / 2;
34    Fmid = find[mid] - y * (Data[mid] - Data[y]) - find[y];
35    Fmid1 = find[mid + 1] - y * (Data[mid + 1] - Data[y]) - find[y];
36    if (x >= Fmid && x < Fmid1)
37    {
38     break;/*mid为目标下标*/
39    }
40    else if (x < Fmid)
41    {
42     high = mid - 1;
43    }
44    else
45    {
46     low = mid + 1;
47    }
48   }
49   /*计算输出值*/
50   result = Data[mid] + (x - Fmid) / (mid + 1 - y);
51  }
52  return result;
53 }
54 void main()
55 {
56  /*进行数据输入*/
57  scanf("%d%d", &n,&m);/*n,m*/
58  long long i;
59  for (i = 0; i < n; i++)
60  {
61   scanf("%d", &Data[i]);/*输入姜的初始高度*/
62  }
63  /*快速从小到大对姜的高度排序*/
64  qsort(Data, n, sizeof(Data[0]), cmp);
65  /*输入m行x，y*/
66  for (i = 0; i < m; i++)
67  {
68   scanf("%lld%d", &x[i], &y[i]);
69  }
70  /*计算寻找数组中各元素的值*/
71  for (i = 1; i < n; i++)
72  {
73   find[i] = find[i - 1] + i * (Data[i] - Data[i - 1]);
74  }
75  for (i = 0; i < m; i++)
76  {
77   printf("%lld\n", Result(x[i], y[i]));
78  }
79 }