AD SUP1 - tacongnam/DylanHarris GitHub Wiki

• Problem: AD - SUP1
• Tag: DP, #TAG Tăng tốc chương trình

Table of Contents Content Input: Output: Example: Solution: Code:

Cho mảng n số nguyên dương a1, a2, ..., an (n≤10^6, ai≤10^6) và số nguyên dương S (S≤10^6). Hãy đếm xem có bao nhiêu cặp ai,aj thỏa mãn ai+aj=S.

Dòng 1: 2 Số nguyên dương n và S
Dòng 2: n số nguyên dương a1, a2, ..., an

Dòng 1: Số cặp ai, aj (i < j) thoả mãn ai + aj = S

Input:

 5 6
 3 2 4 3 4

Output:

 3

Đối với bài toán này chúng ta thường sử dụng thuật toán O(n^2) để giải. Tuy nhiên do n <= 10^6 nên cách làm này không đem lại hiệu quả. Do đó, chúng ta sử dụng một thuật toán mới như sau:
Dễ dàng thấy ai + aj = S <=> ai = S - aj. Do đó ta chỉ cần tìm số các số ai sao cho ai = S - aj (i < j). Vì ai <= 10^6 nên hoàn toàn có thể dùng mảng đếm. Độ phức tạp cho thuật toán mới này là O(n).

 #include <bits/stdc++.h>
 #define maxi 1000005
 using namespace std;
 long long d[maxi],n,a,s,dem;
 int main()
 {
     cin>>n>>s;
     for(int i=1;i<=n;i++)
     {
         cin>>a;
         dem += s - a;
         d[a] ++;
     }
     cout<<dem;
 }