#include "stdafx.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
long long source[101][101];//原始矩阵
long long sourcesum;
long long newm[101][101];//新矩阵
int m, n;
long long a[101], b[101];//a为每行的最大数,b为每列最大数
bool av[101], bv[101];//visited
long long minsum;
//时间判断变量定义
long long totaltime = 0;
int requiretime = 0;
int T;
struct zeroSave {
int x;
int y;
};
vector<zeroSave> zs;
//初始化
void init()
{
memset(source, -1, sizeof(source));
memset(newm, -1, sizeof(newm));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(av, 0, sizeof(av));
memset(bv, 0, sizeof(bv));
minsum = 0;
sourcesum = 0;
zs.clear();
zs.push_back({ 0 });
}
//矩阵输入
void input()
{
cin >> totaltime >> requiretime;
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
int tmp = 0;
cin >> tmp;
source[i][j] = tmp;
sourcesum += tmp;
if (!tmp)
{
newm[i][j] = 0;
}
}
}
//每行每列最大值计算
void maxcal()
{
long long max;
for (int i = 1; i <= m; i++)
{
max = 0;
for (int j = 1; j <= n; j++)
{
if (max < source[i][j])
max = source[i][j];
}
a[i] = max;
}
for (int j = 1; j <= n; j++)
{
max = 0;
for (int i = 1; i <= m; i++)
{
if (max < source[i][j])
max = source[i][j];
}
b[j] = max;
}
}
//矩阵构造
void construct()
{
//从主视图和左视图看,最优矩阵生成
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i] == b[j] && bv[j] == 0)
{
av[i] = 1;
bv[j] = 1;
if (source[i][j] != 0)
{
newm[i][j] = a[i];
break;
}
else
{//碰到合并到0的情况先保存,后面处理
zeroSave temp;
temp.x = i; temp.y = j;
zs.push_back(temp);
break;
}
}
//剩余最大值插入
//行剩余处理
for (int i = 1; i <= m; i++)
{
if (av[i] == 1)
continue;
for (int j = 1; j <= n; j++)
{
if (a[i] <= b[j] && source[i][j] != 0)
{
newm[i][j] = a[i];
av[i] = 1;
break;
}
}
}
//列剩余处理
for (int j = 1; j <= n; j++)
{
if (bv[j] == 1)
continue;
for (int i = 1; i <= m; i++)
{
if (b[j] <= a[i] && source[i][j] != 0)
{
newm[i][j] = b[j];
bv[j] = 1;
break;
}
}
}
}
//对最大值合并到0上时的处理
void zero()
{
for (unsigned k = 1; k < zs.size(); k++)
{
int flag = 0;
//查询当前0的横方向上是否有跟最大值相等的数
for (int i = 1; i <= n; i++)
{
if (a[zs[k].x] == b[i] && i != zs[k].y)//如果存在
{
flag = 1;
break;
}
}
if (flag == 0)//如果不存在
{
//横向分散
for (int i = 1; i <= n; i++)
if (newm[zs[k].x][i] == -1)
{
newm[zs[k].x][i] = a[zs[k].x];
break;
}
//纵向分散
for (int i = 1; i <= m; i++)
if (newm[i][zs[k].y] == -1)
{
newm[i][zs[k].y] = b[zs[k].y];
break;
}
}
}
}
//计算新矩阵大小
void newMatrixSum()
{
minsum = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (newm[i][j] != -1)
minsum += newm[i][j];
else
{
minsum++;
newm[i][j] = 1;
}
}
//oj输出
void oj()
{
cin >> T;
long long diff;
while (T--)
{
init();
input();
maxcal();
construct();
zero();
newMatrixSum();
diff = sourcesum - minsum;
if (totaltime / (double)requiretime > diff)
{
cout << diff << endl;
}
else
{
cout << totaltime / requiretime << endl;
}
}
}
int main()
{
oj();
system("pause");
}
Image Recognition
·814 字·
Archived
相关文章
poj1328 雷达安装
·502 字
Archived
poj1458 最长公共子序列长度
·141 字
Archived
poj2485 Prim算法
·410 字
Archived