题目1

题目链接
题目大意：
在二维坐标系中，每次有两个走法：
1、从(𝑥,𝑦) 到 (𝑥+1, 𝑦+1)；
2、从(𝑥,𝑦) 到 (𝑥-1, 𝑦)；

现在有初始点坐标(a, b)，想要到达坐标(c, d)，想知道最少的步数。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例1行，第一行整数𝑎, 𝑏, 𝑐, 𝑑 (−1e8≤𝑎,𝑏,𝑐,𝑑≤1e8 )

输出：
每个样例一行，输出最小的步数；如果不存在则输出-1；

Examples
input
6
-1 0 -1 2
0 0 4 5
-2 -1 1 1
-3 2 -3 2
2 -1 -1 -1
1 1 0 2

output
4
6
-1
0
3
3

题目解析：
由条件知道，y只能+1或者保持不动，那么先计算y坐标的变化，得到y移动的位置；
剩下的位置只能走x-1的步数，如果x过小则误解，否则x坐标的差距就是剩余步数。

class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            int ok = 0, ans = 0;
            do {
                if (b > d) break;
                ans += d - b;
                a += d - b;
                if (a < c) break;
                ans += a - c;
                ok = 1;
            } while (0);
            cout << (ok ? ans : -1) << endl;
        }
    }
}

题目2

题目链接
题目大意：
n张桌子排成一行，现在Alice开始分配桌子：
1、每次分配的桌子数量依次递增，从1张、2张、3张、、n张，开始分配，直到分配结束；（假如最后一次不足n张，也会分配）
2、第1次分配Alice，然后接下来2次分给Bob，2次分给Alice，不断循环；

问最终Alice和Bob各自能分配到多少张桌子；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200)
每个样例2行，第一行整数𝑛 (2≤𝑛≤1e6）

输出：
每个样例一行，分别输出Alice和bob能分配到的桌子数量。

Examples
input
5
10
6
17
8
1000000

output
5 5
1 5
10 7
3 5
500202 499798

题目解析：
最简单的做法，遍历数组然后不断记住当前是第几次分配和桌子归属，O(N)可以得到Alice和Bob的桌子数量；
这里面我们尝试用更快的方法来求解。
按照题目每次分配桌子规则的要求，我们假设可以分配k次，则有(1+2+3+...+k)=n+z，其中z是一个补偿值，因为最终第k次可能不足，我们用z将其补足；
我们知道前k项和是 (1+k) * k / 2，通过n我们可以快速计算出来k的大小，以及第k次分配的真实数量；
我们令k=sqrt(2 * n)，然后再累加k，直到(1+k)*k/2大于等于n即可；（这个时间复杂度是O(1)）
当我们知道k之后，就可以按照要求，枚举1、2、3、、、k的归属，这样做法的时间复杂度是根号N，即是O（sqrt(N) ）；
但是我们还想追求更快的速度：
我们知道，Alice分得1之后，Bob和Alice会分别获得2个数字；
这样Alice可以得到公式Alice=(0+1) + (4+5) + (8+9) + ...；
Bob可以得到公式Bob=(2+3) + (6+7) + (10+11) + ... ；
我们用int(k/4)可以得到最终公式的项数，剩下的不足4个数字，则可以再手动分配，这样的复杂度是O(1)，整个题目的复杂度可以降为1；

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int k = sqrt(n);
            while ((1 + k) * k / 2 < n) {
                ++k;
            }
            int diffZ = (k + 1) * k / 2 - n; // 最后一个不够的数量
            
            lld ansA = 0, ansB = 0;
            int cntA = (k - 1) / 4 + 1;
            ansA = (0 + 1 + (cntA - 1) * 4 + (cntA - 1) * 4 + 1) * cntA / 2;
            int leftA = k - ((cntA - 1) * 4 + 1);
            if (leftA >= 3) ansA += cntA * 4;
            
            int cntB = (k + 1) / 4;
            ansB = (2 + 3 + (cntB - 1) * 4 + 2 + (cntB - 1) * 4 + 3) * cntB / 2;
            int leftB = k - (cntB * 4 - 1);
            if (leftB >= 3) ansB += cntB * 4 + 2;
            
            if (k % 4 == 0 || k % 4 == 1) ansA -= diffZ;
            else ansB -= diffZ;
            
            cout << ansA << " " << ansB << endl;
        }
    }
}

题目3

题目链接
题目大意：
有n个整数的数组，如果数组存在某个元素，等于该元素前面所有数字的和，则称这个元素为ugly；
比如说数组 [6,3,9,6]，元素 9 = 6 + 3，则元素9是ugly的；
现在可以任意调换数组中元素的位置，但是不能删除或者增加元素，问是否能够让数组没有ugly的元素。
输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤2000)
每个样例2行，第一行整数𝑛 (2≤𝑛≤50）
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎1≤𝑎2≤⋯≤𝑎𝑛≤100)

输出：
每个样例一行，如果无解输出NO，如果有解则输出YES，接下来一行输出调整顺序后的整数数组；

Examples
input
4
4
3 3 6 6
2
10 10
5
1 2 3 4 5
3
1 4 4

output
YES
3 6 3 6
NO
YES
2 4 1 5 3
YES
1 4 4

题目解析：
ugly的要求是前面元素的和，那么前面的元素如果比当前元素大，必然前面元素和会更大；
将整数数组按照从大到小排队，由于整数元素都有>=1，那么从第3个元素开始，必然不会出现ugly元素；
假如a1=a2，那么将最小的元素插入到a2中。（如果数组中所有元素相同，则无解）

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) cin >> a[i];
            sort(a, a + n, greater<int>());
            if (a[0] == a[n - 1]) cout << "NO" << endl;
            else {
                cout << "YES" << endl;
                int tmp = a[1];
                a[1] = a[n - 1];
                a[n - 1] = tmp;
                for (int i = 0; i < n; ++i) cout << a[i] << " ";
                cout << endl;
            }
        }
    }
}

题目4

题目链接
题目大意：
给出整数n，构造一个n x n的整数矩阵，要求：
1、数字是由1、2、3到n^2的整数组成；
2、相邻整数的绝对值差，能形成尽可能多的数字。

输入：
第一行，整数𝑡 表示t个样例 𝑡(1≤𝑡≤49)
每个样例1行，整数𝑛(2≤𝑛≤50)

输出：
每个样例n行，每行n个整数；

Examples
input
2
2
3

output
1 3
4 2
1 3 4
9 2 7
5 8 6

样例解释：
对于n=2，矩阵中相邻整数的差有： |1−3|=2 , |1−4|=3 , |3−2|=1 和 |4−2|=2，一共有3个整数（1、2、3）；

题目解析：
有题目的要求1可以知道，矩阵中差的绝对值，最大值为n^2 - 1，最小值为1，那么不同数最多可能有：1、2、3、、、n^2-1；
那么如何构造一个最大值？首先1放在左上角的位置，然后1的下面和右面放n^2和 n^2-1，这样就构造了两个较大的数字；
同理接下来就可以放再较小的整数。
以整数n=4为例
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
接着
1 15 0 0
16 0 0 0
0 0 0 0
0 0 0 0
然后是
1 15 4 0
16 3 0 0
2 0 0 0
0 0 0 0
最终就是大小交替的效果。
1 15 4 11
16 3 12 7
2 13 6 9
14 5 10 8

class Solution {
    static const int N = 101;
    int a[N][N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int x = 1, y = n * n;
            for (int i = 0; i < n; ++i) {
                if (i % 2 == 0) {
                    for (int j = 0; i - j >= 0; ++j) { // a[i][0]
                        a[i - j][j] = x++;
                    }
                }
                else {
                    for (int j = 0; i - j >= 0; ++j) { // a[i][0]
                        a[i - j][j] = y--;
                    }
                }
            }
            for (int j = 1; j < n; ++j) {
                if ((n + j - 1) % 2 == 0) {
                    for (int i = n - 1; i - j >= 0; --i) { // a[n - i][j]
                        a[i][j + n - 1 - i] = x++;
                    }
                }
                else {
                    for (int i = n - 1; i - j >= 0; --i) { // a[n - i][j]
                        a[i][j + n - 1 - i] = y--;
                    }
                }
            }
            
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) cout << a[i][j] << " ";
                cout << endl;
            }
        }
    }
}

题目5

题目链接
题目大意：
小明和n个人参加比赛，已知n个人的序号分别为1、2、3、、、n；
当n个人中的两个人（序号i和j）内部比赛时，假如i < j,则序号j的选手获胜；（即n个人比赛，序号大者获胜）；
当小明与n个人中的一个比赛时，对于选手i，小明需要花费a[i]时间进行准备，如果有充足时间准备则能胜出，否则会落败；
已知小明一共有m的时间进行比赛，同一时间只能准备一个选手；
最终名次就是胜场较多人数的+1，比如说胜场比小明多的人数一共有5人，那么小明就是第6名；（其他胜场和小明一样多的人，并列第6名）
问小明最的获胜名次最好是多少。（越低越好）

输入：
第一行，整数𝑡 表示t个样例 𝑡(1≤𝑡≤1e4)
每个样例2行，第一行整数 𝑛 and 𝑚 (1≤𝑛≤5⋅1e5)
第二行n个整数𝑎1,𝑎2,…,𝑎𝑛(0≤𝑎𝑖≤1000)

输出：
每个样例1行，输出小明最好的名次。

Examples
input
5
4 401
100 100 200 1
3 2
1 2 3
5 0
1 1 1 1 1
4 0
0 1 1 1
4 4
1 2 2 1

output
1
2
6
4
1

题目解析：
如果时间比较充裕，那么足够准备所有人的比赛；
当时间不够时，通常的选择是优先准备耗时较少的选手；但是在这个题目中，会产生额外的影响：
如果我们没有针对某个选手准备，则该选手都胜场会+1，从而影响到自己的名次。
所以决策是否针对某个选手准备时候，要考虑当前的因素。

由此，我们产生一个简单的策略：
先将准备时间从小到大排序，然后我们从耗费时间小的开始准备，直到某个选手的准备时间不够；
此时我们先不要花时间准备，而是用剩下的时间，将所有能够准备的选手筛出，选择一个胜场数量等于小明胜场+1的选手进行准备；（如果不选他，他就会排在小明前面，选了他则并列）剩下的胜场数相同、胜场数少于小明的，并不会因为小明的选择而影响名次；
然后接下来的选手，由于我们无法准备，所有的选手胜场+1；
至此，我们得到一个解，胜场x，以及每个选手的胜场，得到最终的名次。

class Solution {
    static const int N = 601000;
    pair<int, int> a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, m;
            cin >> n >> m;
            for (int i = 0; i < n; ++i) {
                cin >> a[i].first;
                a[i].second = i;
            }
            sort(a, a + n, lycmp);
            if (a[0].first > m) {
                cout << n + 1 << endl;
                continue;;
            }
            int index = -1, win = 0;
            while (index < n) {
                if (a[index + 1].first <= m) {
                    m -= a[index + 1].first;
                    ++win;
                    ++index;
                }
                else {
                    break;
                }
            }
            
            for (int i = index; i < n; ++i) {
                if (a[index].first + m >= a[i].first && a[i].second == win) {
                    a[i].second -= 1;
                    break;
                }
            }
            int ans = 1;
            for (int i = 0; i < n; ++i) {
                if (i < index && a[i].second > win) ++ans;
                else if (i >= index && a[i].second >= win) ++ans;
            }
            cout << ans << endl;
        }
    }
}