程序员进阶之算法练习（七十八）
题目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;
}
}
}腾讯云开发者
