P1102 A-B 数对

P1102题库链接：https://www.luogu.org/problem/P1102

难度：普及-

算法标签：模拟，数论，排序，HASH，概率论，二分查找

1.朴素 O(n^2) 得分76

将输入所有的数依次作为被减数，除此数外其他数依次作为减数，每当有一组的差为1时，方案数ans + 1

 #include <cstdio>

 using namespace std;

 int main()

 {

     int n, c, s[], ans = ;

     scanf("%d%d", &n, &c);

     for(int i = ; i < n; ++i)

         scanf("%d", &s[i]);

     for(int i = ; i < n; ++i)

     {

         for(int j = ; j < n; ++j)

         {

             if(i == j) continue;

             if(s[i] - s[j] == c) ++ans;

         }

     }

     printf("%d\n", ans);

     return ;

 }

2.桶优化 O(n) 得分84

每输入一个数，所对应的桶增加，因为A - B = C -> A - C = B，枚举每一种A的可能值，从而用A - C求出B，若A，B存在（即桶不为0），则方案数ans += t[A] * t[B]

 #include <cstdio>

 using namespace std;

 int main()

 {

     int n, c, ans = , t[] = {};

     scanf("%d%d", &n, &c);

     for(int i = ; i < n; ++i)

     {

         int x;

         scanf("%d", &x);

         ++t[x];

     }

     for(int i = c; i <= ; ++i)

         if(t[i] !=  && t[i - c] != )

             ans += t[i] * t[i - c];

     printf("%d\n", ans);

     return ;

 }

3.map优化 AC

 #include <cstdio>

 #include <map>

 using namespace std;

 long long a[];

 map<long long, long long> m;

 int main()

 {

     long long n, c, ans = ;

     scanf("%lld%lld", &n, &c);

     for(int i = ; i < n; ++i)

     {

         scanf("%lld", &a[i]);

         ++m[a[i]];

         a[i] -= c;

     }

     for(int i = ; i < n; ++i)

         ans += m[a[i]];

     printf("%lld\n", ans);

     return ;

 }

巴特西

P1102 A-B 数对

最新文章

热门文章