题解 [HDU6746] Civilization(贪心+模拟)

来源：2020 年百度之星·程序设计大赛 - 初赛一

一道贪心 + 细节模拟题

题意很简单，这里不详细写了

观察题目，(n) 只有 500 ，可以 (n imes n) 枚举每个位置作为起点，对于每个位置而言，可以 (6 imes 6) 去枚举周围曼哈顿距离为 (3) 的点，将其都压入一个 vector 中然后排序，显然在城市分配完毕后，选择权值较大的点作为接下来的工作地点是最优的，接下来模拟每个回合的过程就好了，注意，不需要枚举回合，因为大量相邻的回合所提供的贡献都是相同的，可以将其划分一下，就能快速计算了。

当然这种写法也是时间复杂度挺大的，几乎是卡 3s 通过了

代码

const int N = 5e3 + 10;
int a[N][N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n, x, y;
        cin >> n >> x >> y;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
        int ans = INT_MAX;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                vectornum;
                num.push_back(a[i][j]);
                for (int xx = i - 3; xx <= i + 3; xx++)
                    for (int yy = j - 3; yy <= j + 3; yy++) {
                        if (xx <= 0 || yy <= 0 || xx > n || yy > n) continue;
                        if (abs(xx - i) + abs(yy - j) > 3) continue;
                        if (xx == i && yy == j) continue;
                        num.push_back(a[xx][yy]);
                    }
                sort(num.begin() + 1, num.end(), greater());
                while (num.size() <= 9)
                    num.push_back(0);
                int day = (abs(x - i) + abs(y - j) + 1) / 2; //回合
                int sum = 0; //粮食
                int t = num[0]; //当前劳动力
                for (int i = 1; i <= 8; i++) { //枚举人数
                    int target = i * i * 8; //需要多少粮食才能升人口
                    if (sum < target) {
                        int temp = (target - sum + t - 1) / t; //还需要工作几个回合
                        sum += temp * t; //加上temp回合的贡献
                        day += temp; //加上temp回合
                    }
                    t += num[i]; //贪心加上新来的人口
                }
                ans = min(ans, day);
            }
        cout << ans << "
";
    }
}

题解 [HDU6746] Civilization(贪心+模拟)

相关推荐