眾所周知，小蔥同學(xué)擅長(zhǎng)計(jì)算，尤其擅長(zhǎng)計(jì)算一個(gè)數(shù)是否是另外一個(gè)數(shù)的倍數(shù)。
但小蔥只擅長(zhǎng)兩個(gè)數(shù)的情況，當(dāng)有很多個(gè)數(shù)之后就會(huì)比較苦惱。
現(xiàn)在小蔥給了你 n 個(gè)數(shù)，希望你從這 n 個(gè)數(shù)中找到三個(gè)數(shù)，使得這三個(gè)數(shù)的和是 K 的倍數(shù)，且這個(gè)和最大。
數(shù)據(jù)保證一定有解。

輸入格式
第一行包括 2 個(gè)正整數(shù) n,?K。
第二行 n 個(gè)正整數(shù)，代表給定的 n 個(gè)數(shù)。

輸出格式
輸出一行一個(gè)整數(shù)代表所求的和。

數(shù)據(jù)范圍
1≤n≤10^5,
1≤K≤10^3,
給定的 n 個(gè)數(shù)均不超過 10^8
輸入樣例：
4 3
1 2 3 4
輸出樣例：
9

代碼如下：

#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int f[4][N]; vector<int> a[N]; int main() {int n,m;cin>>n>>m;for (int i = 0;i<n;i++){int x;cin>>x;a[x%m].push_back(x);}memset(f,-0x3f,sizeof(f));f[0][0] = 0;for (int i = 0;i<m;i++){sort(a[i].begin(),a[i].end());reverse(a[i].begin(),a[i].end());for (int u = 0;u<3 &&u <a[i].size();u++){int t = a[i][u];for (int j = 3;j>=1;j--)for (int k = 0;k<m;k++){f[j][k] = max(f[j][k],f[j-1][((k-t)%m+m)%m]+t);}}}cout<<f[3][0]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的AcWing 1234. 倍数问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。