【HDU 1735】字数统计（贪心，有缺陷的一道题）

野性酷女 2023-06-01 14:57 14阅读 0赞

### 题目分析： ###

1.  告知有m段，第一行一定带领一段，所以要找出另外m-1段。
2.  由于题目要求最少有多少字被破坏，所以我们要找出的m-1段要求被破损的最少，即是“好”的部分最多。
3.  满足一段开头的第i行，首部两格数字一定是0。
4.  满足条件3的行数可能大于等于m-1。
5.  何时“好”的部分最多？第i-1行末尾0的个数最多。（最理想情况）

### 解题思路： ###

ans = 0的个数 - “好”的个数最多的m-1行的0的个数 - 2\*m（m段） - 最后一行末尾0的个数。

### 备注 ###

本人认为此题有一个漏洞，或者说本人未考虑清楚。如下：

若某行首行两数字为0，其上一行全0，该怎么处理？

若有大佬知道，望指教一二。

【注】不知道hdu什么破烂机制，这题必须要写成循环不然不给过。

### 代码如下（G++）： ###

#include <bits\stdc++.h> using namespace std; typedef long long ll; char a[10005][110];//存矩阵 int main(){ ios::sync_with_stdio(false); int n,m,l; //不知道hdu什么破烂机制，必须要写成循环不然不给过 while(cin >> n >> l >> m){ int ans = 0; //输入矩阵，ans为0的个数 for(int i = 1;i <= n; ++i) for(int j = 1;j <= l; ++j) cin >> a[i][j]; if(a[i][j] == '0') ans++; //当某行首部出现两个0，num存上一行末尾0的个数 int num[10010] = {0}; int k = 0; for(int i = 2;i <= n; ++i) if(a[i][2] == '0' && a[i][1] == '0'){ for(int j = l;j >= 1; --j){ if(a[i-1][j] == '1') break; num[k]++; } k++; } //选出末尾含0最多的m-1行 sort(num,num+k); int cnt = 0; for(int i = k-1;cnt < m-1&&i >= 1; i--){ ans -= num[i]; cnt++; } //减去最后一行末尾的0 for(int i = l; i >= 1; i--){ if(a[n][i] == '1') break; ans--; } //还需要减m行首部的2个0，其中1个必定是第一行 cout << ans-2*m << endl; } return 0; }

转载于:https://www.cnblogs.com/zhangjiuding/p/11452414.html