题目要求的是最少多少次能够涂完不是蓝色的方格,只需要将蓝色方格的坐标扫一遍
求出差值最小的就行了,当然连续的要跳过。
那么答案就是将每个连续的整块对这个最小差值做除法,如果能整除那么就直接加上整除的值,
否则就再加1.
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N]; int main(){ int n, m; cin >> n >> m; for(int i = 1; i <= m; i ++) cin >> a[i]; sort(a + 1, a + 1 + m); int minn = 0x3f3f3f3f; for(int i = 1; i <= m; i ++){ if(a[i] - a[i - 1] - 1 == 0) continue; minn = min(minn, a[i] - a[i - 1] - 1); } int ans = 0; for(int i = 1; i <= m; i ++){ if(a[i] - a[i - 1] - 1 == 0) continue; if((a[i] - a[i - 1] - 1) % minn == 0){ ans += (a[i] - a[i - 1] - 1) / minn; } else{ ans += (a[i] - a[i - 1] - 1) / minn; ans ++; } } if((n - a[m]) % minn == 0) ans += (n - a[m]) / minn; else{ ans += (n - a[m]) / minn; ans ++; } cout << ans << endl; return 0; }