contents
Problem
現在 pizza 上有 m 個橄欖,請問是否能均分 m 塊,使得每一塊皆有一個橄欖。
1 2 3 4
|
12 3 2 8 11 12 4 4 5 7 11
|
Sample Output
Solution
窮舉其中兩個相鄰橄欖中的所有分割點,檢查一下即可。
稍微估價一下,點多窮舉次樹就少,點少切割成功的機率就高,所以算法總不會太差。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
#include <stdio.h> #include <algorithm> using namespace std; int main() { int n, m, A[65536]; while (scanf("%d %d", &n, &m) == 2) { for (int i = 0; i < m; i++) scanf("%d", &A[i]); A[m] = A[0] + n; int ret = 0, div = n/m; for (int i = A[0]; i < A[1]; i++) { int d = i, ok = 1; for (int j = 1; j <= m; j++) { if (d < A[j] && A[j] <= d + div) d += div; else { ok = 0; break; } } if (ok) { ret = 1; break; } } puts(ret ? "S" : "N"); } return 0; } 12 3 2 8 11 12 4 4 5 7 11 */
|
近期评论