首页 > 代码库 > 第5届ACM校赛—矩阵

第5届ACM校赛—矩阵

2024-07-05 05:07:16   223人阅读

                                                             矩阵

题目描述

给定一个n x m 的矩阵，每次操作，你可以对矩阵的某一个元素加上或减去一个整数值d，求最小的操作次数，使得矩阵的所有元素都相同，如果不能实现，输出-1。

输入

输入包含多组测试数据，对于每组测试数据：

第一行为三个整数  , m≤500,1≤d≤10000）。

接下来 m 个整数，第 行第 个整数为ij(1  ij≤10)。

当n=m=d=0 时代表输入结束。

输出

对于每组测试数据，输出一个整数，为最小操作次数，如果不能实现，输出-1。
64-bit，用long long 定义，请不要使用__int64 和%I64d。


PS：要想找到最小的次数，只能让整个矩阵，变成中间大的数；

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[250001];
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int n,m,s;
   while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        if(n==0&&m==0&&s==0)
            break;
        for(int i = 0;i<n*m;i++)
            scanf("%d",&a[i]);

        qsort(a,n*m,sizeof(a[0]),cmp);

       long long int sum = 0;
        int flag = 0;
       long long int mid = a[(n*m)/2];
        for(int i = 0;i<n*m;i++)
        {
           if((mid-a[i])%s!=0)
           {
               flag = 1;
               break;
           }
            if(mid>a[i])
            {
                sum += (mid - a[i])/s;
            }
            else if(mid<=a[i])
            {
               sum += (a[i]-mid)/s;
            }
        }
        (flag==1)?puts("-1"):printf("%lld\n",sum);

    }
    return 0;
}


联系
我们