自己又写了一个新方向的代码, 但是效果很不理想啊.... (1个Case WA, 8个Case TLE)
1044.cpp
// Frame by SkyShi
// john11, posted
#include<iostream>
#include<algorithm>
#define N 100009
#define M 10009
using namespace std;
int n,m,x[N],y[M],ans[M];
int amcnam[2][3];
// 排序函数
bool cmp(int x, int y)
{
return x < y;
}
// 绝对值函数
int abs(int number)
{
if(number < 0) {
return -number;
}
return number;
}
// 冒泡排序函数
void convert(void)
{
int one;
int i, k;
for(i=0; i<2; i++) {
for(k=0; k<(2-i); k++) {
if(amcnam[1][k] > amcnam[1][k+1]) {
one = amcnam[1][k];
amcnam[1][k] = amcnam[1][k+1];
amcnam[1][k+1] = one;
one = amcnam[0][k];
amcnam[0][k] = amcnam[0][k+1];
amcnam[0][k+1] = one;
} else if(amcnam[1][k] == amcnam[1][k+1]) {
if(amcnam[0][k] > amcnam[0][k+1]) {
one = amcnam[1][k];
amcnam[0][k] = amcnam[0][k+1];
amcnam[0][k+1] = one;
}
}
}
}
return;
}
// 获取排序后的amcnam[0][0]的serial
int getindex(int ptr)
{
for(int i = 0; i < 3; i++) {
if(x[ptr-1+i] == amcnam[0][0]) {
return i+1;
}
}
return -1;
}
// 二分求解函数 (?)
int nearby(int a)
{
int base=1, limit=n; // 范围的最低值和最高值
int ptr;
for(;;) {
ptr = (base+limit) >> 1; // 右移一位等同于除以二
for(int i=0; i<3; i++) {
amcnam[0][i] = x[ptr-2+i];
amcnam[1][i] = abs(x[ptr-2+i]-a);
if(amcnam[1][i] == 0) {
return amcnam[0][i];
}
}
convert();
// 警告! 以下代码可能将极度迷惑! (????)
if(limit-base+1 <= 3) {
return amcnam[0][0];
} else {
switch(getindex(ptr)) {
case 1:
limit = ptr;
break;
case 2:
return amcnam[0][0];
break;
case 3:
base = ptr;
break;
}
}
}
return 0;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i];
}
cin>>m;
for(int i=0;i<m;i++){
cin>>y[i];
}
sort(x, x+n, cmp); // 元素由小到大排序
for(int i=0;i<m;i++){
cout<<nearby(y[i])<<endl;
}
//system("pause"); // Debug
return 0;
}