我AC了.
但很惭愧, 这个AC是照抄其他用户提供的题解得到的. (但这里又不是洛谷) 答主Tim的题解使用了标准的二分算法. 所以我将题解修改为了个人的代码风格并加上了注释. 希望能有所启迪.
1044ans.cpp
// by Tim (http://oj.noi.cn/oj/index.php/main/download/1044/c%252B%252B.txt/0/solution_path)
//#define _CRT_SECURE_NO_WARNINGS // VS 2019
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int a[100001];
int b[10001];
// 真正的二分求解函数
int cz(int l, int r, int m)
{
// 如果求解范围的差小于等于1, 则输出最终结果
if (r - l <= 1) {
// 三目运算符, 判断运算符需要特别解释.
// 如m - a[l] <= a[r], 如果满足a[l] <= a[r]
// 则等同于m-1, 否则等同于m-0
// (表达式)?(值1):(值2) 构成三目运算符
// 如m ? a[l] : a[r]
// 如果m为1 (即"true"), 则这个运算符返回a[l], 否则返回a[r]
// 代码解读后如下:
// if(a[l] <= a[r]) {
// m--;
// }
//
// if(m != 0) {
// m -= a[l];
// } else {
// m -= a[r];
// }
//
// return m;
// 这段代码具体表达什么意思还有待解读.
return m - a[l] <= a[r] - m ? a[l] : a[r];
}
int mid = (l + r) / 2;
if (m > a[mid]) {
// 如果数字大于中间的元素
return cz(mid, r, m); // 求解范围开始 = mid, 即舍去了大于一半的部分
}
else {
// 如果数字大于中间的元素
return cz(l, mid, m); // 求解范围结束 = mid, 即舍去了小于等于一半的部分
}
return 0;
}
int main() {
int m, n, num;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &num);
//b[i]=cz(1,n,num);
printf("%d\n", cz(1, n, num));
}
//system("pause");
return 0;
}