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

题目分析：

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;
} 

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

原文：https://www.cnblogs.com/zhangjiuding/p/11452414.html