Powers of two（multiset的运用）

【题目】

Powers of two

B - Powers of two

Time limit : 2sec / Memory limit : 1024MB

Score : 600 points

Problem Statement

Takahashi has N balls with positive integers written on them. The integer written on the i-th ball is Ai. He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2. Note that a ball cannot belong to multiple pairs. Find the maximum possible number of pairs that can be formed.

Here, a positive integer is said to be a power of 2 when it can be written as 2t using some non-negative integer t.

Constraints

• 1≤N≤2×105
• 1≤Ai≤109
• Ai is an integer.

Input

Input is given from Standard Input in the following format:

N
A1 A2 … AN

Output

Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2.

Sample Input 1

3
1 2 3

Sample Output 1

1

We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls. Note that we cannot pair the second ball with itself.

Sample Input 2

5
3 11 14 5 13

Sample Output 2

2

【题解】

题意：给定长度为n的序列，输出最多的两两组合之和为2的整次方的对数。

按理说我当时也是从后往前匹配的思路啊，但是为什么wa了...谜（留个悬念）

做法就是存入序列multiset自动排序，然后从大到小寻找是否存在可匹配满足条件的项，如果存在，答案+1，并删去匹配项。

认识了新容器 --- multiset，加深了迭代器的印象（太久没用都忘了）。

【代码】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define og(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define Pi acos(-1)
#define eps 1e-8
using namespace std;
typedef long long int ll;
const int maxn=2*1e5+5;
const ll inf=0x3f3f3f3f;
const int mod=1e9+7;
multiset <int> s;
int main()
{
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x; scanf("%d",&x);
        s.insert(x);
    }
    int ans=0;
    while(!s.empty())
    {
        multiset <int> ::iterator it=s.end();
        it--;
        int x=*it;
        s.erase(it);
        for(n=1;n<=x;n*=2);
        if(s.find(n-x)!=s.end())
            ans++,s.erase( s.find(n-x) );
    }
    printf("%dn",ans);
    return 0;
}

最后

以上就是闪闪绿茶为你收集整理的Powers of two（multiset的运用）的全部内容，希望文章能够帮你解决Powers of two（multiset的运用）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。