题目1
题目链接
题目大意:
给出一个数组长度为n,每次可以选择若干个数字,将其数字+1;
问最少需要操作几次,才能让整个数组内的元素值相等。
输入:
第一行,样例数𝑡 (1≤𝑡≤1e4)
每个样例两行,第一行整数𝑛 (1≤𝑛≤50)
第二行𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出:
每个样例一行,输出最小的操作次数。
Examples
input
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
output
3
4
1
题目解析:
由贪心的思想,由最大值减去最小值就能得到最多需要操作次数k;
因为其他数字和最大值的差距,不会比这个值更大,肯定可以在k次操作内完成。
class Solution {
static const int N = 200010;
string str;
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];
}
int valMin = a[0], valMax = a[0];
for (int i = 1; i < n; ++i) {
valMin = min(valMin, a[i]);
valMax = max(valMax, a[i]);
}
printf("%d\n", valMax - valMin);
}
}
}
ac;
题目2
题目链接
题目大意:
给出三个正整数a、b、c,现在可以对三个整数中的一个乘以正整数m;
这个操作只能执行一次,要求是最后三个成为等差数列。
比如说原来三个整数是10、5、30,那么可以将第二个乘以4,那么三个整数变为10、20、30,可以形成等差数列。
输入:
第一行样例数𝑡 (1≤𝑡≤1e4)
每个样例一行,包括整数𝑎, 𝑏, 𝑐 (1≤𝑎,𝑏,𝑐≤1e8).
输出:
如果有解,输出YES;如果无解,输出NO;
Examples
input
11
10 5 30
30 5 10
1 2 3
1 6 3
2 6 3
1 1 1
1 1 2
1 1 3
1 100000000 1
2 1 1
1 2 2
output
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
题目解析:
最终想要形成的是等差数列,即是a-b=b-c;
由此可以推出来:
new_a=2b-c;
new_b=(a+c)/2;
new_c=2b-a;
那么就只要看最终new_a、new_b、new_c是不是原来的a、b、c的整数倍即可。
trick:
需要注意,由于m是正整数,所以new_a必须大于等于a才行。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int a, b, c;
cin >> a >> b >> c;
int ok = 0;
int new_a = 2 * b - c, new_b = (a + c) / 2, new_c = 2 * b - a;
if (new_a >= a && new_a % a == 0) {
ok = 1;
}
if (new_b >= b && new_b * 2 == (a + c) && (new_b % b == 0)) {
ok = 1;
}
if (new_c >= c && new_c % c == 0) {
ok = 1;
}
cout << (ok ? "YES" : "NO") << endl;
}
}
}
ac;
题目3
题目链接
题目大意:
给出n个正整数的数组a,现在每次可以对数组的一个元素操作:a[i]=a[i]除以2,向下取整;
问经过若干次操作之后,能否将数组变成1到n的排列,即数组是由整数1到n组成。
输入:
第一行样例数𝑡 (1≤𝑡≤1e4)
每个样例两行,第一行整数𝑛 (1≤𝑛≤50)
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出:
如果有解,输出YES;如果无解,输出NO;
Examples
input
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22
output
YES
NO
YES
NO
NO
YES
题目解析:
由贪心的思想可以知道,如果给出的整数a中存在1到n的整数,应该优先使用这些整数;
接着从剩下的整数中,不断挑选整数进行除2操作,如果遇到没有出现过的整数,则停止除2操作;
因为即使存在另外整数除以2会得到相同值的整数,在得到相同值的时候,他们已经是等价的整数了。
class Solution {
static const int N = 10010;
string str;
int a[N];
int cnt[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[i + 1] = 0;
}
int ok = 1;
for (int i = 0; i < n; ++i) {
while (a[i]) {
if (a[i] <= n && cnt[a[i]] == 0) {
cnt[a[i]] = 1;
break;;
}
a[i] /= 2;
}
if (!a[i]) {
ok = 0;
}
}
cout << (ok ? "YES" : "NO") << endl;
}
}
}
ac;
题目4
题目链接
题目大意:
小明在玩游戏,游戏中有n个怪兽站成一排,每个怪兽的血量为a[i];
小明可以释放技能,每次技能可以伤害其中1个怪兽2点血,以及左边或者右边相邻1点血;
比如说3个怪兽血量为[1,3,1],则小明可以对中间怪兽释放两次技能,则可以把所有怪兽的血量清零;(怪兽血量为0仍然可以释放技能)
现在只需要把其中2个怪兽的血量清理,问最少需要放几次技能;
输入:
第一行,整数n (2≤𝑛≤2⋅1e5)
第二行,n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e6)
输出:
最少需要的技能次数;
Examples
input
5
20 10 30 10 20
output
10
题目解析:
这个题目用dp来解决,dp[i][0]表示前i怪兽打死1个的最小次数,dp[i][1]表示前i个怪兽打死2个的最小次数;
对于第i个怪物,有打死和不打死两种可能,不打死的话直接dp[i-1]转移,打死的话有多种可能:单独打死,和i-1一起打死,或者和i-2一起打死;
根据上面两种情况,得到两个状态的转移方程,即可解决问题,复杂度O(N);
但是这个题目不需要动态规划,同样可以解决:
打怪兽只有两种可能,分开打死和一起打死,分开打死取数组最小2个元素即可,一起打死有下面两种可能:
1、两个怪兽是相邻的,可以假设血量为x和y(x<y),先只考虑对y放技能的情况,算出打死两个怪物的最少次数,然后考虑有多少个1/2的伤害可以替换为2/1;
2、两个怪兽是不相邻的,那么必然是打击中间的怪兽,掉两边的血;当有一个怪物死亡后,就可以瞄准剩下的怪物;(解决血量为[1,10,3]这样的情况)
复杂度同样为O(N),并且不要考虑状态转移,实现更加简单;
class Solution {
static const int N = 201010;
int a[N], dp[N][2];
int check(int x, int y) {
int maxItem = max(x, y);
int minItem = min(x, y);
int cnt = 0;
if (minItem * 2 <= maxItem) {
cnt = (maxItem + 1) / 2;
}
else {
cnt = minItem - (minItem * 2 - maxItem) / 3;
}
return cnt;
}
public:
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0xfffffff;
for (int i = 1; i < n; ++i) {
ans = min(ans, check(a[i], a[i - 1]));
if (i >= 2) {
ans = min(ans, min(a[i], a[i - 2]) + (a[i] + a[i - 2] - min(a[i], a[i - 2]) * 2 + 1) / 2);
}
}
sort(a, a + n);
ans = min(ans, (a[0] + 1) / 2 + (a[1] + 1) / 2);
cout << ans << endl;
}
}
ac;
题目5
题目链接
题目大意:
给出一个n x m的矩阵,由' . '和' * '组成;
现在想把矩阵内的星号全部调整到前面,比如说:
.*.
.**
.**
调整为
**.
**.
*..
先填充第1列,然后再填充第2列,以此类推,填充顺序为从上到下;
每次移动可以选择一个' * '移动到任意为' . '的位置;
现在有q次操作,每次会输入2个位置x和y,会把对应位置的元素修改为另外一个符号;
现在想知道每次操作之后,最少需要的移动次数;(每次操作的结果保留在矩阵中)
输入:
第一行,整数 𝑛, 𝑚 and 𝑞 (1≤𝑛,𝑚≤1000;1≤𝑞≤2⋅1e5)
接下q行,每行2个整数 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖≤𝑛;1≤𝑦𝑖≤𝑚)
输出:
输出q行,每行是操作后的最少移动次数;
Examples
input
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2
output
3
4
4
3
4
5
5
5
题目解析:
按照题目的要求,假设矩阵中有sum个星号,容易知道最终排成的元素会集中在j=(sum-1)/n列和i=(sum-1)%m行中;
并且我们得到一个快速计算移动次数的方法,假如前j列,前i行中一共有ans个星号,那么最少移动次数就是sum-ans;
容易知道q次操作中,每次操作之后影响str[x][y]这个位置,并且会导致sum变化,从而导致ans变化;
但是由于每次操作只能修改1个字符,我们只需判断下sum变化之前,最后一个位置是否为星号,就可以快速计算得到ans;
这样每次操作之后,计算sum和ans的复杂度只需要O(1);
注意,每次操作之后,有两种可能会影响ans:
1、操作的字符就在最终排列的结果里面;
2、影响sum之后,sum关联到的对应的最后一个位置;
class Solution {
static const int N = 1010;
vector<string> str;
public:
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; ++i) {
string tmp;
cin >> tmp;
str.push_back(tmp);
}
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (str[i][j] == '*') {
++sum;
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (j * n + i < sum) {
if (str[i][j] == '*') {
++ans;
}
}
else {
break;
}
}
}
while (q--) {
int x, y;
cin >> x >> y;
--x;
--y;
if (str[x][y] == '*') {
str[x][y] = '.';
if (y * n + x < sum) {
--ans;
}
int j = (sum - 1) / n, i = (sum - 1) % n;
if ((i != x || j != y) && str[i][j] == '*') {
--ans;
}
--sum;
}
else {
str[x][y] = '*';
++sum;
if (y * n + x < sum) {
++ans;
}
int j = (sum - 1) / n, i = (sum - 1) % n;
if ((i != x || j != y) && str[i][j] == '*') {
++ans;
}
}
cout << sum - ans << endl;
}
}
}
ac;
网友评论