Mircea has n pictures. The i-th picture is a square with a side length of si centimeters. He mounted each picture on a square piece of cardboard so that each picture has a border of w centimeters of cardboard on all sides. In total, he used c square centimeters of cardboard. Given the picture sizes and the value c, can you find the value of w? A picture of the first test case. Here c=50=52+42+32, so w=1 is the answer. Please note that the piece of cardboard goes behind each picture, not just the border. Input The first line contains a single integer t (1≤t≤1000) — the number of test cases. The first line of each test case contains two positive integers n (2≤n≤2⋅105) and c (1≤c≤1018) — the number of paintings, and the amount of used square centimeters of cardboard. The second line of each test case contains n space-separated integers si (1≤si≤104) — the sizes of the paintings. The sum of n over all test cases doesn't exceed 2⋅105. Additional constraint on the input: Such an integer w exists for each test case. Please note, that some of the input for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). Output For each test case, output a single integer — the value of w which was used to use exactly c squared centimeters of cardboard. Example inputCopy 10 3 50 3 2 1 1 100 6 5 500 2 2 2 2 2 2 365 3 4 2 469077255466389 10000 2023 10 635472106413848880 9181 4243 7777 1859 2017 4397 14 9390 2245 7225 7 176345687772781240 9202 9407 9229 6257 7743 5738 7966 14 865563946464579627 3654 5483 1657 7571 1639 9815 122 9468 3079 2666 5498 4540 7861 5384 19 977162053008871403 9169 9520 9209 9013 9300 9843 9933 9454 9960 9167 9964 9701 9251 9404 9462 9277 9661 9164 9161 18 886531871815571953 2609 10 5098 9591 949 8485 6385 4586 1064 5412 6564 8460 2245 6552 5089 8353 3803 3764 outputCopy 1 2 4 5 7654321 126040443 79356352 124321725 113385729 110961227 Note The first test case is explained in the statement. For the second test case, the chosen w was 2, thus the only cardboard covers an area of c=(2⋅2+6)2=102=100 squared centimeters. For the third test case, the chosen w was 4, which obtains the covered area c=(2⋅4+2)2×5=102×5=100×5=500 squared centimeters. c++实现

#include <iostream>
#include <vectorusing namespace std;

long long calculateCardboard(vector<int>& sizes, int w) {
    int n = sizes.size();
    long long c = 0;
    for (int i = 0; i < n; i++) {
        c += (2 * w + sizes[i]) * (2 * w + sizes[i]);
    }
    return c;
}

int findBorderWidth(vector<int>& sizes, long long c) {
    int n = sizes.size();
    int low = 0, high = 1e9;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (calculateCardboard(sizes, mid) >= c) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long c;
        cin >> n >> c;
        vector<int> sizes(n);
        for (int i = 0; i < n; i++) {
            cin >> sizes[i];
        }
        int w = findBorderWidth(sizes, c);
        cout << w << endl;
    }
    return 0;
}

该代码首先定义了两个辅助函数：calculateCardboard用于计算给定边界宽度w时所需的卡纸面积，findBorderWidth用于二分查找合适的边界宽度w。

在主函数中，首先读取测试用例的数量t，然后循环读取t个测试用例。每个测试用例中，首先读取画作的数量n和已使用的卡纸面积c，然后读取每个画作的尺寸。接下来，调用findBorderWidth函数找到合适的边界宽度w，并输出结果。