观察可知,嫌犯无论怎么操作,都不会改变数组的总和,真凶操作一次,就会使得数组总和+1
因此,我们可以使用哈希表统计n个数组的总和,出现次数为一次的,即为真凶,操作次数,其实就是嫌犯所在的数组之和与真凶所在的数组之和的差值
C++
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=100;
int n,w[N],m;
int main(){
cin>>n>>m;
map<int,int>mp;
for(int i=0;i<n;i++){
int x;
int sum=0;
for(int j=0;j<m;j++){
cin>>x;
sum+=x;
}
mp[sum]++;
w[i]=sum;
}
int pos,sum1,sum;
for(int i=0;i<n;i++){
if(mp[w[i]]==1){
pos=i+1;
sum=w[i];
}
else{
sum1=w[i];
}
}
int cnt=abs(sum1-sum);
cout<<pos<<" "<<cnt<<endl;
return 0;
}
Java
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
long minus=0;
long ma=0;
for(int i=1;i<=n;i++){
long tor=0;
for(int j=1;j<=m;j++){
int a=sc.nextInt();
tor+=a;
}
if(minus==0&&ma==0){
minus=tor;
continue;
}
if(minus!=0&&tor!=minus){
long dif=Math.abs(tor-minus);
i=tor>minus?i:1;
System.out.print(i+" "+dif);
return;
}
}
}
}
Python
n, m = map(int, input().split())
a = []
for i in range(n):
a.append(sum(map(int, input().split())))
r = 0
for i in range(n):
if a[i] > a[r]:
print(i+1, a[i]-a[r])
break
elif a[i] < a[r]:
print(r+1, a[r]-a[i])
break
易容之术,一直是古今武侠小说中常见的招数,有这么一个名为塔子的年轻人,他精通易容之术,但是他内心的正义感告诉他,要匡扶正义,于是他与东厂进行了合作,决定在众多会易容之术嫌犯之中抓住真凶! 塔子拿到了n个长度为m的数组,分别表示所有嫌犯的五官参数,其中有一个数组描述了真凶的五官参数。初始状态下每个数组都是相同的,易容嘛,长一样也很合理()。每一次易容有若干次以下操作:
1.嫌犯由于比较弱,只能选择两个元素,其中一个加1,另一个减1
2.真凶技高一筹,他会选择两个元素,其中一个加2,另一个减1。
第一行输入两个正整数n和m,代表数组的数量、以及每个数组的长度 接下来的n行,每行输入m个正整数 aij,代表第i个数组的第j个元素
1≤n∗m≤1e5
1≤aij≤1e9
1<n
输出两个正整数u和v,分别表示第u个数组是真凶的五官信息,以及凶手对其易容操作了v次
输入
3 4
1 2 3 4
2 1 4 3
6 2 2 2
输出
3 2
说明
初始的3个数组都是[2,2,3,3]。
第3个数组是真凶的五官参数
嫌疑人对第一个数组操作1次,第四个数加1,第一个数减1,数组变成[1,2,3,4]。
嫌疑人对第二个数组操作1次,第三个数加1,第二个数减1,数组变成[2,1,4,3]。
真凶对第三个数组操作2次,第一个数加2,第三个数减1; 第一个数加2,第四个数减1,数组变成[6,2,2,2]。
1s, 1024KiB for each test case.