当前位置：首页 > news >正文

HDOJ 1735：字数统计 ← 贪心

news 来源：原创 2025/6/29 22:43:44

【题目来源】
https://acm.hdu.edu.cn/showproblem.php?pid=1735

【题目描述】
一天，淘气的 Tom 不小心将水泼到了他哥哥 Jerry 刚完成的作文上。原本崭新的作文纸顿时变得皱巴巴的，更糟糕的是由于水的关系，许多字都看不清了。可怜的 Tom 知道他闯下大祸了，等 Jerry 回来一定少不了一顿修理。现在 Tom 只想知道 Jerry 的作文被“破坏”了多少。
Jerry 用方格纸来写作文，每行有 L 个格子。（图 1 显示的是 L=10 时的一篇作文，’X’ 表示该格有字，该文有三个段落）。

图 1

图 2

图 2 显示的是浸水后的作文，‘O’ 表示这个位置上的文字已经被破坏。可是 Tom 并不知道原先哪些格子有文字，哪些没有，他唯一知道的是原文章分为 M 个段落，并且每个段落另起一行，空两格开头，段落内部没有空格（注意：任何一行只要开头的两个格子没有文字就可能是一个新段落的开始，例如图 2 中可能有 4 个段落）。
Tom 想知道至少有多少个字被破坏了，你能告诉他吗？

【输入格式】
测试数据有多组。每组测试数据的第一行有三个整数：N（作文的行数 1≤N≤10000），L（作文纸每行的格子数 10≤ L≤100），M（原文的段落数 1≤M≤20），用空格分开。
接下来是一个 N×L 的位矩阵 (Aij)（相邻两个数由空格分开），表示被破坏后的作文。其中 Aij 取 0 时表示第 i 行第 j 列没有文字（或者是看不清了），取 1 时表示有文字。你可以假定：每行至少有一个 1，并且所有数据都是合法的。

【输出格式】
对于每组测试输出一行，一个整数，表示至少有多少文字被破坏。

【输入样例】
10 10 3
0 0 0 1 1 1 0 1 1 0
1 1 0 0 0 1 1 1 0 0
0 0 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 0 0 0
1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 0

【输出样例】
19

【算法分析】
● 任何一行只要开头的两个格子没有文字就可能是一个新段落。但是，在输入样例中，原本没有文字或被破坏后看不清处均用 0 表示，所以输入样例原本“可能”有 4 个段落。之所以说“可能”，是因为不知道输入样例中的 0 是原本没有文字，还是被破坏而看不清。
● 好在题目给定了约束：“给定了原文段落数”、“所有数据都是合法的”、“段落内部没有空格”。所以，可根据这些约束条件利用贪心算法思想进行分析、编码，得到至少有多少文字被破坏。
● 难点在于算法代码中 sec[++idx] 数组的理解，以及循环变量为什么终至 idx-(M-2)？因为，sec[++idx] 存储的是每段末尾的 0 的个数。这些段既包含原文的段落数，又包含被污染后被误认的段落数。最后一段的 sec[] 值即下午代码中的 tail 值，已由 ans-=tail 给减去了。且 sec[1]=0。故有效的 sec[] 值的数为 M-2。

【算法代码】

#include <iostream>
#include <algorithm>
using namespace std;const int maxn=1e4+5;
int sec[maxn];
int a[105];
int N,L,M;int main() {while(cin>>N>>L>>M) {int ans=0;int tail=0; //number of 0 at the end of the previous lineint idx=0; //id of paragraphfor(int i=1; i<=N; i++) {for(int j=1; j<=L; j++) {cin>>a[j];if(a[j]==0) ans++;}if(!a[1] && !a[2]) sec[++idx]=tail;for(int j=L; j>=1; j--) {if(a[j]==1) {tail=L-j;break;}}}ans-=2*M;ans-=tail;sort(sec+1,sec+idx+1);for(int i=idx; i>=idx-(M-2); i--)ans-=sec[i];cout<<ans<<endl;}return 0;
}/*
in:
10 10 3
0 0 0 1 1 1 0 1 1 0
1 1 0 0 0 1 1 1 0 0
0 0 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 0 0 0
1 1 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 0out:
19
*/

【参考文献】
https://blog.csdn.net/andream7/article/details/104226879
https://blog.51cto.com/u_15740602/5542315
https://www.cnblogs.com/yinbiao/p/9398073.html

相关文章：