#419 Div2 Problem C Karen and Game (贪心 && 暴力)
2024-09-05 16:11:46
题目链接:http://codeforces.com/contest/816/problem/C
题意 :给出一个 n*m 的变化后的矩阵,变化前矩阵的元素全是0,变化的规则是选择其中的一行或者一列将元素进行加一操作,问你最少用几步操作能将全零的矩阵变成一开始输入的矩阵,如果无法做到则输出-1,否则输出操作的总次数以及具体的操作步骤。
分析 :如果跟着题意顺着想如何从全零矩阵进行变化那可能比较费劲,不如将一开始输入的矩阵进行减的操作(即逆操作)使其最后变成全零矩阵可能会更简单操作,因为只是在原始矩阵进行变化。那如何减呢?可以注意到如果我们先枚举行的话,比如第1行,试想一下第一行最多能够进行多少次减的操作?不难想到这一行中最小的数便是可以进行的操作数,那我们只要枚举所有的行和列找出每一行的最小值,如果最小值>0则进行模拟操作并且记录方便最后的输出。但是这里有个坑,就是题目要求的是最小的操作总数,那对于一个所有元素都相同但是行数和列数都不相同的矩阵便有区别了,例如矩阵的元素都是1,但是n>m,如果此时先枚举1~n那便不是最优了,所以要注意枚举行和列的先后顺序,取决于n和m的相对大小。还有一个就是题目有无法实现就输出-1的情况,这里我们只要在一开始输入矩阵的时候记录所有元素的和,然后在减的时候我们不难得出减的总合,如果减的总和!=原矩阵元素总和,则说明无法实现。
#include<bits/stdc++.h> using namespace std; ; int G[maxn][maxn]; int n, m; int row[maxn]; int col[maxn]; ; ; inline void col_work() { ; i<m; i++){ int Min = 0x3f3f3f3f; ; j<n; j++){ if(G[j][i] < Min) Min = G[j][i]; } ){ col_cnt++; col[i]++; ; j<n; j++){ G[j][i]--; } i--;//因为减一次可能还不够,所以再判断一次这列是否可以再减 } } } inline void row_work() { ; i<n; i++){ int Min = 0x3f3f3f3f; ; j<m; j++){ if(G[i][j] < Min) Min = G[i][j]; } ){ row_cnt++; row[i]++; ; j<m; j++){ G[i][j]--; } i--; } } } int main(void) { ; scanf("%d %d", &n, &m); ; i<n; i++){ ; j<m; j++){ scanf("%d", &G[i][j]); sum += G[i][j]; } } if(n > m){ col_work(); row_work(); }else{ row_work(); col_work(); } if((row_cnt * m + col_cnt * n)!=sum){//无法实现的情况 puts("-1"); ; } printf("%d\n", row_cnt+col_cnt); ; i<n; i++){ while(row[i]--)//这里用一个row数组来记录这一行进行了多少次减操作,col数组也是同样道理 printf(); } ; i<m; i++){ while(col[i]--) printf(); } ; }
最新文章
- BlockingQueue 阻塞队列,很有用的一种
- Javascript模式(第四章函数)------读书笔记
- ConurrentHashMap和Hashtable的区别
- mysql的存储过程
- Spring MVC 事务配置
- Java基础-内部类-为什么局部和匿名内部类只能访问局部final变量
- Python中时间的处理之——timedelta篇
- 小鸟哥哥博客 For SAE
- android开发之重写Application类
- Qt 学习之路 :动态视图
- 使用Python在2M内存中排序一百万个32位整数
- ACM:图BFS,迷宫
- 浅谈测试rhel7新功能时的感受及遇到的问题【转载】
- PVM的安装和编译PVM程序
- Spring事务管理—aop:pointcut expression解析(转)
- Spring 自带的定时任务Scheduled
- 【Git之旅】2.Git对象
- odoo12 物流 自动计算运费 ,采购销售使用不同计量单位自动换算
- Java 11 究竟比 8 快了多少?
- MySQL 5.7 以上版本默认禁止 0000-00-00 的日期
热门文章
- ros3。3教程 入门到高级
- 查看主机CPU信息
- 【Linux 驱动】简单字符设备驱动架构(LED驱动)
- cannot convert from pointer to base class &#39;QObject&#39; to pointer to derived class &#39;subClass&#39; via virtual base &#39;baseClass&#39;
- JS中property与attribute的区别
- java 工具类使用
- mycat 笔记
- 14.AutoMapper 之依赖注入(Dependency Injection)
- Vue的双向数据绑定的原理
- 使用layer弹窗和layui表单做新增功能