Codeforces Round #748 (Div. 3) C.D

C.Save More Mice

题目大意： 在数轴上的 1 1 1位置为起始位置，有一只猫； n n n为终点，有一个洞。数轴上有一些老鼠。每次先选择一只老鼠向右移动一位，然后猫向右移动一位。当猫当前位置有老鼠，老鼠会被吃掉；如果老鼠移动到洞，则老鼠会被保护起来。求最多能保护多少只老鼠？

思路： 贪心思想，每次只能移动一步，那么要救尽可能多的老鼠，应当从最右侧的老鼠开始移动，那么按照这个顺序，开始模拟这个过程即可。

#include<bits/stdc++.h>
using namespace std;
 
int arr[400005];
 
signed main(){
	int t; cin >> t;
	while(t--){
		int n, k; cin >> n >> k;
		for(int i = 0; i < k; i++){
			cin >> arr[i];
		}
		sort(arr, arr + k);
		int sum = 0, ans = arr[k - 1];
		for(int i = k - 1; i >= 0; i--){
			if(n - arr[i] <= ans) sum++, ans -= (n - arr[i]);
            else{
				if(arr[k - 1] - arr[i] < ans) sum++;
				break;
			}
		}
		cout << sum << endl;
	}
	return 0;
}
           

D1.All are Same

题目大意：给定数组，求一个 k k k，每次对数组中的某个数字改变 k k k，最终能够使数组全部相等。

a % k = b % k → ( a − b ) % k = 0 a \% k = b \% k \rightarrow (a - b)\%k = 0 a%k=b%k→(a−b)%k=0

思路： 求一个最大值一个最小值，做差后与除去最小值的每个元素求最大公因数即可。如果整个序列相同，则输出 − 1 -1 −1。

#include <bits/stdc++.h>
using namespace std;

int arr[45];

inline void solve(){
    int n; cin >> n;
    int maxn = -1000005;
    int minn = 1000005;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        minn = min(minn, arr[i]);
        maxn = max(maxn, arr[i]);
    }
    int ans = maxn - minn;
    for (int i = 0; i < n; i++){
        if (arr[i] != minn) ans = __gcd(ans, arr[i] - minn);
    }
    if (ans == 0){
        cout << -1 << endl;
        return;
    }
    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}