Find the nth digit(二分查找) - HDU 1597

#include <stdio.h>

int main()
{
    //静态存储区默认值为0，66000是调整的值，只要不WA，可以尝试从大往小调
    static int sum[66000];
    int index;
    int position;
    //初始化表，这张表记录了每个区间的位置
    //0,1(0+1),3(1+2),6(3+3)...
    for (int i = 1; i < 66000; ++i) {
        sum[i] = sum[i - 1] + i;
    }

    int count;
    scanf("%d", &count);

    while (count--) {
        scanf("%d", &position);
        index = -1;
        int l = 1;
        int r = 66000;
        //二分查找
        while (1) {
            //每次进来算出新的中间位置
            int mid = (l + r) / 2;
            //正好在区间里面，注意这里是index=mid
            if (sum[mid] < position && sum[mid + 1] >= position) {
                index = mid;
                break;
            }
            //如果在左区间，则将r指针指向中间
            if (position <= sum[mid])
                r = mid - 1;
            //如果在右区间，则将l指针指向中间
            if (sum[mid + 1] < position)
                l = mid + 1;
        }
        //n为位置，减去区间值，则是剩余的值，如101，如果区间值为90
        //则剩余11，这个11代表的肯定是12345678912这样的串
        int value = position - sum[index];
        //取余，去掉1-9这样的重复串
        value %= 9;
        if (value == 0) {
            value = 9;
        }
        printf("%d\n", value);
    }
}