单选题库

const int MAXN = 1005; // 最大位数
struct BigInt {
    int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
    int len;     // 数字长度
 
    BigInt() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
 
// 比较两个高精度数的大小
int compare(BigInt a, BigInt b) {
    if (a.len != b.len) return a.len > b.len ? 1 : -1;
    for (int i = a.len - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}
 
// 高精度减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c;
    for (int i = 0; i < a.len; i++) {
        c.d[i] += a.d[i] - b.d[i];
        if (c.d[i] < 0) {
            c.d[i] += 10;
            c.d[i+1]--;
        }
    }
    c.len = a.len;
    while (c.len > 1 && c.d[c.len-1] == 0) c.len--;
    return c;
}
 
// 高精度除法 (a/b，返回商和余数)
pair<BigInt, BigInt> div(BigInt a, BigInt b) {
    BigInt q, r; // q是商，r是余数
 
    if (compare(a, b) < 0) { // 如果 a < b，商为0，余数为a
        q.len = 0;
        r = a;
        return make_pair(q, r);
    }
 
    // 初始化余数r为a的前b.len位
    r.len = b.len;
    for (int i = a.len - 1; i >= a.len - b.len; i--) {
        r.d[i - (a.len - b.len)] = a.d[i];
    }
 
    // 逐位计算商
    for (int i = a.len - b.len; i >= 0; i--) {
        // 把下一位加入余数
        if (r.len == 1 || r.d[0] != 0) {
            for (int j = r.len; j > 0; j--) {
                r.d[j] = r.d[j-1];
            }
            _______________________________ // 横线处
        } else {
            r.d[0] = a.d[i];
            r.len = 1;
        }
 
        // 计算当前位的商
        while (compare(r, b) >= 0) {
            r = sub(r, b);
            q.d[i]++;
        }
    }
 
    // 确定商的长度
    q.len = a.len - b.len + 1;
    while (q.len > 1 && q.d[q.len-1] == 0) q.len--;
 
    // 处理余数前导零
    while (r.len > 1 && r.d[r.len-1] == 0) r.len--;
 
    return make_pair(q, r);
}

int randomPartition(std::vector<int>& arr, int low, int high) {
    int random = low + rand() % (high - low + 1);
    std::swap(arr[random], arr[high]);
 
    int pivot = arr[high];
    int i = low - 1;
 
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}
 
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

const int MAX_COINS = 10;
int result[MAX_COINS] = {0};  // 假设最多10种面额
 
int find_coins(const vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end(), greater<int>());
 
    int n = coins.size();
 
    for (int i = 0; i < n; ++i) {
        int coin = coins[i];
        int num = amount / coin;
        result[i] = num;
        amount -= num * coin;
        if (amount == 0) break;
    }
 
    cout << "找零方案如下：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
    }
 
    return 0;
}

double sqrt_binary(long long n, double epsilon = 1e-10) {
    if (n < 0) {
        throw invalid_argument("输入必须为非负整数");
    }
 
    if (n == 0 || n == 1) return n;
 
    // 阶段 1
    long long low = 1, high = n;
    long long k = 0;
 
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long mid_sq = mid * mid;
 
        if (mid_sq == n) {
            return mid;
        } else if (mid_sq < n) {
            k = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
 
    long long next_k = k + 1;
    if (next_k * next_k == n) {
        return next_k;
    }
 
    // 阶段 2
    double low_d = (double)k;
    double high_d = (double)(k + 1);
    double mid;
 
    while (high_d - low_d >= epsilon) {
        mid = (low_d + high_d) / 2;
        double mid_sq = mid * mid;
 
        if (mid_sq < n) {
            low_d = mid;
        } else {
            high_d = mid;
        }
    }
 
    double result = (low_d + high_d) / 2;
    long long check_int = (long long)(result + 0.5);
    if (check_int * check_int == n) {
        return check_int;
    }
 
    return result;
}

int binary_search_last_occurrence(const vector<int>& lst, int target) {
    if (lst.empty()) return -1;
 
    int low = 0, high = lst.size() - 1;
 
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (lst[mid] <= target) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
 
    if (lst[low] == target)
        return low;
    else
        return -1;
}