Civilization

传送门
题意是给出一个n*n的矩阵，表示每回合如果有居民就生产的粮食数，以及一个起点x，y，然后主人公可以没回合进行选择，是移动还是建造城市，如果建造城市，那么主人公就不能再移动，也就是说，只能建造一个城市，然后在这个城市进行生产粮食，最后得到人口，再派遣到周围去生产粮食。求得到人口为9时的最小回合数

之前题意没懂，然后第二遍看题时，以模拟的思维进行，每回合进行一次操作，要么进行建造，要么移动。
但其实建造只有一次，那么我们可以求出在所有点进行建造时的最小回合数，然后再求出这个点到起点的距离，求出要走多少回合。
对于每个点进行建造，首先该点必须考虑，然后在周围的点里找出最大的8个点，按照降序进行生产粮食。模拟即可

所以说，可以从全局考虑，不用按照题意去模拟，按照贪心，从整体角度考虑

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 505;
int a[N][N];
void solve(){
    int n, x, y, ans = 0x3f3f3f3f;
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            std::vector<int> v;
            v.push_back(a[i][j]);
            for(int k = i - 3; k <= i + 3; k++) {
                for(int z = j - 3; z <= j + 3; z++) {
                    if(k < 1 || k > n || z < 1 || z > n) continue;
                    if(abs(k - i) + abs(z - j) > 3) continue;
                    if(k == i && j == z) continue;
                    v.push_back(a[k][z]);
                }
            }
            sort(v.begin() + 1, v.end());
            reverse(v.begin() + 1, v.end());
            v.resize(9);
            int each = v[0], tot = 0, times = 0;
            for(int k = 1; k <= 8; k++) {
                int need = 8 * k * k;
                if(tot < need) {
                    int waittimes = (need - tot + each - 1) / each;
                    times += waittimes;
                    tot += each * waittimes; 
                }
                each += v[k];
            }
            int dis = abs(i - x) + abs(j - y);
            times += (dis + 1) / 2; // 需要一回合建造城市
            ans = min(ans, times);
        }
    }
    printf("%d
", ans);
}
int main(){
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}