hdu 1735(贪心) 统计字数

戳我穿越：http://acm.hdu.edu.cn/showproblem.php?pid=1735

对于贪心，二分，枚举等基础一定要掌握的很牢，要一步一个脚印走踏实

这是道贪心的题目，要有贪心的意识。

首先将所有为0的地方统计，因为是求最小的字数，所有最后一行后面的0可以看为空格直接减掉，

因为有m段(一定包括第一行)，再减去m*2，最后枚举每行，将至少前两个为0的上一行的最后有多少

的0统计起来排序，再依次减去前m-1个大的，这样就保证了得到的答案是符合条件中最小的

code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int yj[][],lsy[];

 bool cmp(int x,int y){return x>y;}

 int main()

 {

     int n,m,x,sum,ans,i,j,k,flag;

     while (~scanf("%d %d %d",&n,&m,&x))

     {

         sum=;

         for (i=;i<=n;i++)

         {

             for (j=;j<=m;j++)

             {

                scanf("%d",&yj[i][j]);

                if (!yj[i][j])

                   sum++;

             }

         }

         //printf("%d\n",sum);

         for (i=m;i>=;i--)

         {

             if (!yj[n][i]) sum--;

             else break;

         }

         //printf("%d\n",sum);

         k=;

         for (i=;i<=n;i++)

         {

             ans=;flag=;

             if (!yj[i][]&&!yj[i][])

             {

                 flag=;

                 for (j=m;j>=;j--)

                 {

                     if (!yj[i-][j])

                         ans++;

                     else

                         break;

                 }

             }

             if (flag)

                lsy[k++]=ans;

         }

         sum-=*x;x--;

         /*for (i=1;i<k;i++)

             printf("%d ",lsy[i]);

         printf("\n");*/

         sort(lsy+,lsy+k,cmp);

         for (i=;i<=x;i++)

             sum-=lsy[i];

         printf("%d\n",sum);

     }

     return ;

 }

巴特西

hdu 1735(贪心) 统计字数

最新文章

热门文章