2277 问题 B: [蓝桥杯][2018年第九届真题]倍数问题
发布时间
阅读量：
阅读量
众所周知, 小葱同学在计算方面非常出色, 尤其善于判断一个数是否是另一个数的倍數. 然而小葱仅在處理兩個數值時表现得非常流暢, 遇到多個數時則會感到比較吃力. 現在小蔥將會提供给你n個數, 請你從中挑出三個數, 使得這三個數的總和能被K整除, 并使這個總和達到最大值. 數據保證一定有解
输入
从标准输入读入数据。
第一行包含两个正整数n,K。
第二行为n个正整数组成的序列。
请输出。
请将结果输出至标准输出端口。
请将结果计算后以一行一个整数的形式显示出来。
样例输入：
4 3
1 2 3 4
样例输出：
9
在解题报告中发现深度优先搜索（DFS）的方法显得效率不够高。因为k的值远小于1000我发现这种方法可行于是考虑将所有具有相同余数的元素进行存储对于前两层的所有组合情况在第三层计算剩余项数目时使用3*k - i - j取模运算更为高效最困难的部分在于判断三个数值是否相等的情况需要特别注意以确保结果准确
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=100010;
int n,k;
int a[N];
bool st[N];
int cnt[N];
int ans=-1e9;
vector<int>vv[1010];
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
vv[((a[i])%k)].push_back(a[i]);
}
for(int i=0;i<k;i++)
{
if(!vv[i].size())
continue;
sort(vv[i].begin(),vv[i].end());
reverse(vv[i].begin(),vv[i].end());
}
for(int i=0;i<k;i++){
if(!vv[i].size())
continue;
for(int j=0;j<k;j++)
{
if(!vv[j].size())
continue;
if(vv[(3*k-i-j)%k].size())
{
int t=(3*k-i-j)%k;
if(i==j&&j==t)
{
if(vv[0].size()<3)
continue;
else
ans=max(ans,vv[i][0]+vv[i][1]+vv[i][2]);
}
else if(i==j||j==t||i==t)
{
if(i==j)
{
if(vv[i].size()<2)
continue;
ans=max(ans,vv[i][0]+vv[i][1]+vv[t][0]);
}
if(i==t)
{
if(vv[i].size()<2)
continue;
ans=max(ans,vv[i][0]+vv[i][1]+vv[j][0]);
}
if(j==t)
{
if(vv[j].size()<2)
continue;
ans=max(ans,vv[j][0]+vv[j][1]+vv[i][0]);
}
}
else
{
ans=max(ans,vv[i][0]+vv[j][0]+vv[t][0]);
}
}
}
}
cout<<ans<<endl;
return 0;
}全部评论 (0)
还没有任何评论哟~