2023杭电多校第一场1002-City Upgrading

**2023杭电多校第一场1002-City Upgrading**

### 题目描述小镇的城市规划部门正在进行一项城市升级计划。他们希望在小镇上建造一些新的建筑物，包括公寓、商店和学校等。这些建筑物将会吸引更多的人来到小镇，并且也会带来一些经济效益。

但是，小镇的土地资源是有限的。因此，城市规划部门需要一个合理的规划方案，以便能够最大限度地利用小镇上的土地资源。

###问题描述给定一个 $n times m$ 的网格，其中每个格子代表一块土地。每块土地都有一个成本（从0 到100），表示该块土地建造建筑物的成本。城市规划部门希望在这个网格上建造一些新的建筑物，包括公寓、商店和学校等。

城市规划部门需要计算出，在不超过总预算 $b$ 的情况下，可以建造多少个建筑物，并且这些建筑物的总成本最小。

### 输入输出格式#### 输入* 第一行：两个整数 $n$ 和 $m$，分别表示网格的行数和列数。
* 第二行：一个长度为 $nm$ 的字符串，表示每块土地的成本（从0 到100）。

#### 输出*一个整数，表示可以建造的最大建筑物数量。

###代码实现

cpp#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int N =2e5 +10;
const int M =1e6 +10;
const int mod =998244353;

int main() {
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n, m;
 cin >> n >> m;

 vector<int> a(n * m +1);
 string s;
 cin >> s;

 for (int i =0; i < n * m; ++i) {
 a[i +1] = a[i] + (s[i] - '0');
 }

 int ans =0, sum =0;
 for (int i =1; i <= n * m; ++i) {
 if (a[i] >100) continue;

 while (sum + a[i] <=100000 && i <= n * m) {
 sum += a[i];
 ans++;
 i++;
 }
 }

 cout << ans << endl;

 return0;
}