列表

详情


NC213899. 牛牛想起飞

描述

给定一个长度为 n 的序列和一个长度为 n 的序列,对于序列中的每一个数字a_i,牛牛都可以进行以下操作:
(1) 将数字 a_ia_i 变成
(2) 将数字 a_ia_i 变成 a_i - b_i
牛牛很懒,所以每个数字只能最多进行一次操作,甚至不操作。现在给出一个数字 y ,牛牛想要知道在做合理的操作后能得到模 y 意义下的最大序列和是多少。
换句话说,设  是最终得到的 数组的样子,你要使得  结果最大化。
做出这道题他就能起飞,你能帮帮他吗?

输入描述

第一行输入
第二行输入 n 个整数
第三行输入 n 个整数

输出描述

输出能得到模 y 意义下的最大序列和

示例1

输入:

3 100
1 2 3
1 1 1

输出:

9

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C(clang11) 解法, 执行用时: 21ms, 内存消耗: 1016K, 提交时间: 2020-12-31 22:56:48

#include<stdio.h>
int max(int a,int b){
	if(a>b)return a;
	else{
		return b;
	}
}
int main(){
	int n,y;
	scanf("%d%d",&n,&y);
	int maxi,i,a[n],b[n];
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	for(i=0;i<n;i++)scanf("%d",&b[i]);
	int z=0,x=0,c=0;
	for(i=0;i<n;i++){
		z+=a[i];
		x+=a[i]+b[i];
		c+=a[i]-b[i];
		maxi=max(maxi%y,max(z%y,max(x%y,c%y)))%y;
	}
	printf("%d",maxi);
}

JavaScript(V8 6.0.0) 解法, 执行用时: 78ms, 内存消耗: 19648K, 提交时间: 2021-01-01 00:41:49

let [n, mod] = readline().split(' ').map(i=>Number(i))

let a = readline().split(' ').map(i=>Number(i))
let b = readline().split(' ').map(i=>Number(i))

let sum = 0
for(let i=0;i<n;i++) {
    sum += a[i]
    sum%=mod
}
let max = sum
for(let i=0;i<n;i++) {
    sum +=b[i]
    sum %= mod
    max = Math.max(max,sum)
}


print(max)

C++(clang++11) 解法, 执行用时: 43ms, 内存消耗: 504K, 提交时间: 2021-01-01 10:10:14

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,y;
	cin>>n>>y;
	int i,j;
	int p,q;
	int num=0;
	
	for(i=0;i<n;i++){
		cin>>p;
		num+=p;
		num=num%y;
	}
	int max=num;
	
	for(i=0;i<n;i++){
		cin>>p;
		num+=p;
		num=num%y;
		if(num>max){
			max=num;
		}
	}
	
	printf("%d",max); 
	
	return 0;
}

Python3(3.9) 解法, 执行用时: 105ms, 内存消耗: 14464K, 提交时间: 2021-01-01 12:29:01

n,y = map(int,input().split())
la = list(map(int,input().split()))
lb = list(map(int,input().split()))
total = 0
for num in la:
    total += num
    total %= y
ans = total
for num in lb:
    total += num
    total %= y
    ans = max(ans,total)
print(ans)

上一题