Đề bài:
Thuật toán:
- Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
- Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
- Chú ý đề bài cho dãy A đôi một khác nhau nhé.
Code:
- C++ (xem)
#include <bits/stdc++.h> using namespace std; const int oo = 500001; const int MAXN = 10001; int i, j, n, m, a[MAXN], tmp, res, f[oo]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a+1,a+n+1); tmp = 0; for (int i = a[1]; i <= m; i++) { if ((tmp < n) && (i >= a[tmp+1])) tmp++; f[i] = a[tmp]; } for (int i = 1; i<= n-2; i++) { for (int j = i+1; j <= n-1; j++) { tmp = m - a[i] - a[j]; if (tmp < 1) continue; tmp = f[tmp]; if (tmp <= a[j]) continue; res = max(res, a[i] + a[j] + tmp); } } cout << res; return 0; } |
- Pascal (xem)
CONST fin=''; fout=''; VAR res, i, j, n, m, x, min: longint; a, ok: array[1..1000000] of longint; f: text; BEGIN Assign(f,fin); Reset(f); Readln(f,n,m); min:=maxlongint-1; For i:=1 to n do Begin Read(f,a[i]); ok[a[i]]:=a[i]; If a[i]<min then min:=a[i]; End; Close(f); For i:=min+1 to 1000000 do If ok[i]=0 then ok[i]:=ok[i-1]; res:=0; For i:=1 to n-1 do For j:=i+1 to n do Begin x:=m-a[i]-a[j]; If x>0 then Begin If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x]; End; End; Assign(f,fout); Rewrite(f); Writeln(f,res); Close(f); END. |
Speak Your Mind