程序员进阶之算法练习（七十四）
题目1
题目链接 题目大意： 给出一个整数n，现在可以对整数执行一个操作： 选择整数上两个不同位数的数字交换位置，然后移除整数最右边一位的数字； 重复这个过程，直到整数只剩下1位； 现在想知道这个剩下的数字最小可能为多少。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例俩行，第一行 整数 𝑛 (10≤𝑛≤1e9)
输出： 每个样例一行，剩下最小的数字；
Examples input 3 12 132 487456398 output 2 1 3
题目解析： 右边第二位是必胜位，每次都选择其他位数的数字进行交换，在只剩下2位数字的时候，将第一位和第二位交换，然后会去掉右边的数字，剩下原来右边第二位的数字； 也就是说，当时数字位数大于等于3的时候，可以选择整数上最小的数字，将这个数字放在右边第二位，再采用上面的策略必然可以留下来； 当数字位数只有2位时，留下来的数字必然是最右边的数字；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n < 99) {
cout << n % 10 << endl;
}
else {
int ans = 9;
while (n) {
ans = min(ans, n % 10);
n /= 10;
}
cout << ans << endl;
}
}
}
}
ac;题目2
题目链接 题目大意： 给出整数a，b，c，满足a<b<c； 构造三个整数x，y，z，满足： x mod y = a; y mod z = b; z mod x = c;
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，𝑎 , 𝑏, 𝑐 (1≤𝑎<𝑏<𝑐≤1e8).
输出： 每个样例一行，输出满足的𝑥 , 𝑦, 𝑧 (1≤𝑥,𝑦,𝑧≤1e18)
Examples input 4 1 3 4 127 234 421 2 7 8 59 94 388 output 12 11 4 1063 234 1484 25 23 8 2221 94 2609
题目解析： 题目要求里面并没有包括x、y、z的大小关系，那么如果要满足x%y = a，最简单的做法就是x=a，并且满足x<y； 同理，可以得到y%z=b，会有y=b，并且满足y<z； 但是在z%x=c，假如我们令z=c，满足z<x则会出现异常，因为由前面两个已经可以递推得到x<y<z；并且由于a<c，x如果为a是无法得到c的；
由于a<c的约束，我们先考虑满足z%x=c的限制，即是令z=c，并且满足z<x； 接着是y%z=b，可以令y=b，由于b<c=z，所以这个也能够满足； 剩下的就是x%y=a，已知y=b，那么有x%b=a，即是x=b*k + a；
此时要满足x=bk + a，z<x，可以令k=c，那么有x=cb+a；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
lld a, b, c;
cin >> a >> b >> c;
cout << (c * b + a) << " " << b << " " << c << endl;
}
}
}
ac;题目3
题目链接 题目大意： 给出n x m的矩阵a，a[i][j]是一个整数； 现在需要选择任意两列进行交换，现在想知道是否存在一种交换方式，满足： 交换之后，每一行的元素，从左到右都是非递减的；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例第一行是整数𝑛 and 𝑚 (1≤𝑛,𝑚≤2⋅1e5) 接下来会有n行m列的整数 𝑎[𝑖,𝑗] (1≤𝑎[𝑖,𝑗]≤1e9)；
输出： 每个样例一行，输出满足的交换位置；（可以交换相同位置） 如果无解则输出-1；
Examples input 5 2 3 1 2 3 1 1 1 2 2 4 1 2 3 2 2 2 1 1 1 2 3 6 2 1 5 4 3 2 1 1 2
output 1 1 -1 1 2 1 3 1 1
题目解析： 先考虑一维的情况，给出一个数组，交换任意两个数字，然后将数组变成非递减； 由于每次只能选择交换相同位置或者两个位置，也就是说要么影响2个数字，要么不影响，那么可以先计算一遍最长非递减的子序列得到长度k； 根据k和n的区别，如果n-k>2，那么就是必然无解； 但是由于k可以等于n、n-1、这几种情况是比较难以决策如何选择出来两个位置； 考虑到只有一次交换（2个位置），那么假如将数组直接排序，是不是也可以通过这个来对比得到这个位置？ 假如排序之后，将有序数组和原数组对比，得到若干个不匹配的位置，如果不同数大于2则无解，如果不同数为2则就是交换的两个位置，如果不同数为0则不需要交换；（这里不存在不同数位1的情况）
基于上面一维的分析，我们可以推导到二维数组的情况。 当我们从上到下去遍历每一行元素时，当我们第一次找到存在2个位置不同的时候，我们就将这位置作为最终的交换位置； 将整个矩阵相应列进行交换，最后判断结果是否符合要求。
注意：如果某一行完全匹配（不同数为0），此时应该先忽略，去找不同位置为2的行；
class Solution {
static const int N = 201010;
vector<int> a[N];
vector<int> b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
a[i].clear();
b[i].clear();
for (int j = 0; j < m; ++j) {
int x;
scanf("%d", &x);
a[i].push_back(x);
b[i].push_back(x);
}
}
vector<int> diff;
bool ans = true;
for (int i = 0; i < n; ++i) {
sort(a[i].begin(), a[i].end());
if (!diff.size()) {
for (int j = 0; j < m; ++j) {
if (a[i][j] != b[i][j]) {
diff.push_back(j);
}
}
}
}
if (diff.size() > 2) {
ans = false;
}
else if (!diff.size()){
diff.push_back(0);
diff.push_back(0);
}
else {
for (int i = 0; i < n; ++i) {
int x = diff[0], y = diff[1];
int tmp = b[i][x];
b[i][x] = b[i][y];
b[i][y] = tmp;
for (int j = 0; j < m; ++j) {
if (a[i][j] != b[i][j]) {
ans = false;
}
}
}
}
if (ans) {
cout << diff[0] + 1 << " " << diff[1] + 1 << endl;
}
else {
cout << (-1) << endl;
}
}
}
}
ac;题目4
题目链接 题目大意： 在一个n x m的方格矩阵中，小明要从左上角（1，1）到右下角（n，m），小红要从左下角（n，1）到右上角（1，m）； 每个相邻格子的行动代价是1； 小红先出发，沿路中每个经过格子都会放下一个传送器，这个不需要代价； 小明晚出发，小明如果站在某个有传送器的格子，那么可以花费1代价，传送到另外一个有传送器的格子； 问小红和小明到达目的，总的代价最小为多少；
输入： 第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000) 每个样例第一行 整数 𝑛, 𝑚 ( (1≤𝑛,𝑚≤1e5)
输出： 每个样例一行，输出最小的总代价；
Examples input 7 7 5 5 7 1 1 100000 100000 57 228 1 5 5 1 output 15 15 0 299998 340 5 5
题目解析： 在没有传送器的情况下，小红和小明的路径总代价都是n+m； 假设小红不考虑小明，按照最短路径到达，总代价是n+m；然后小明借助小红的路径，理论上能节省的最大路径是max(n, m)-1，总的代价就是n+m+max(n, m)-1； 此时路径应该就是小红先走到(1, 1)，再走到(1, m）； 有没有可能小红为了让小明能够尽可能传送，特意绕路？不会，因为小红要走过的路才能让小明传送；所以一旦远离小红的最优路径n+m，所有给小明节省的代价，其实都是不划算的. 注意：边界情况要考虑，n=1 和 m=1。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n == 1 || m == 1) {
if (n == m) cout << 0 << endl;
else cout << max(n, m) << endl;
}
else cout << (n + m - 2) * 2 - max(n, m) + 2 << endl;
}
}
}
ac;题目5
题目链接 题目大意： 给出包括n个非负整数的数组a，我们可以计算这个数组的beauty值： 将数组每个元素除以k，向下取整得到这个元素的beauty值，数组的beauty值等于所有元素的beauty值总和； 现在给出n、k、数组beauty值b和数组元素累加和s，求是否能够构造数组a；
输入： 第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000) 每个样例第一行 整数 𝑛, 𝑘, 𝑏, 𝑠 (1≤𝑛≤1e5, 1≤𝑘≤1e9, 0≤𝑏≤1e9, 0≤𝑠≤1e18).
输出： 每个样例一行，如果无解输出-1；如果有解则输出n个整数；𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤1e18)
Examples input 8 1 6 3 100 3 6 3 12 3 6 3 19 5 4 7 38 5 4 7 80 99978 1000000000 100000000 1000000000000000000 1 1 0 0 4 1000000000 1000000000 1000000000000000000 output -1 -1 0 0 19 0 3 3 3 29 -1 -1 0 0 0 0 1000000000000000000
题目解析： 为了方便思考，我们先考虑数组只有3个元素的情况，那么有： a1 + a2 + a3 = s ; a1/k + a2/k + a3/k = b;
那么我们可以令a1=k * b，先保证条件b可以满足； 因为除以k的原因，接下来a1到a3，都可以增大k-1的大小而且不影响b的值； 那么s的上限就是k * b + n * (k - 1)，下限就是k * b； 满足这里的条件就有解。
思考： 如何证明正确性？假设a1/k + a2/k，a2需要大于k，那么将a2-k，并将a1+k是等价的；
注意： 超过int32，不过样例已经覆盖了这样的case。
class Solution {
static const int N = 201010;
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n, k, b, s;
cin >> n >> k >> b >> s;
lld maxSum = k * b + n * (k - 1);
if (maxSum < s || b * k > s) {
cout << -1 << endl;
}
else {
s -= b * k;
for (lld i = 0; i < n; ++i) {
lld tmp = min(k - 1, s);
s -= tmp;
if (i == 0) tmp += b*k;
cout << tmp << " ";
}
cout << endl;
}
}
}
}
ac;腾讯云开发者
