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;
}