HDU 1735字数統計-貪欲-[解題報告]C++
欲張りは、最初に2つの0がある限り、その前の行の最後に何個連続した0があるかを判断し、前の行の最後に0の数を大きくから小さく並べ替える(破壊文字数を最小にするため、1(決定可能な文字数)に変換できる0の数を最大にする必要がある).最後に特殊な処理をして、最初の行の先頭と最後の行の末尾の0でいいです.
コードは次のとおりです.
変換元:http://www.acmerblog.com/hdu-1735-%E5%AD%97%E6%95%B0%E7%BB%9F%E8%AE%A1-2718/
コードは次のとおりです.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int mess[10001][101];
struct Tom
{
int num, zero;
} save[10001];
int cmp(const void *x, const void *y)
{
return (*(struct Tom*)y).zero - (*(struct Tom*)x).zero;
}
int main()
{
#ifdef test
freopen("sample.txt", "r", stdin);
#endif
int m, n, l;
while(scanf("%d%d%d", &n, &l, &m) != EOF)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<l; j++)
scanf("%d", &mess[i][j]);
}
int cct=0;
if(mess[0][0]==0&&mess[0][1]==0)
mess[0][0]=mess[0][1]=2;// 0
for(int i=1; i<n; i++)
if(mess[i][0]==0&&mess[i][1]==0)
{
save[cct].num = i;
save[cct].zero = 0;
for(int j=l-1; j>=0; j--)
if(mess[i-1][j]==0)
++save[cct].zero;
else break;
++cct;
}
qsort(save, cct, sizeof(save[0]), cmp);
for(int i=0; i<m-1; i++)
{
int ii = save[i].num;
mess[ii][0]=mess[ii][1]=2;// 0 1
for(int j=l-1; j>=0; j--)
if(mess[ii-1][j]==0)
mess[ii-1][j] = 2;// 0 1
else break;
}
int cct_zero=0;
for(int i=l-1; i>=0; i--)
if(mess[n-1][i]==0)// 0
mess[n-1][i]=2;
else break;
for(int i=0; i<n; i++)
for(int j=0; j<l; j++)
if(mess[i][j]==0)
++cct_zero;
printf("%d
", cct_zero);
}
return 0;
}
変換元:http://www.acmerblog.com/hdu-1735-%E5%AD%97%E6%95%B0%E7%BB%9F%E8%AE%A1-2718/