ICPC（6）A - Doubles

发表于

ICPC（6）A - Doubles

As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 unique positive integers and asked to determine how many items in each list are twice some other item in the same list. You will need a program to help you with the grading. This program should be able to scan the lists and output the correct answer for each one. For example, given the list

1 4 3 2 9 7 18 22
your program should answer 3, as 2 is twice 1, 4 is twice 2, and 18 is twice 9.

Input

The input will consist of one or more lists of numbers. There will be one list of numbers per line. Each list will contain from 2 to 15 unique positive integers. No integer will be larger than 99. Each line will be terminated with the integer 0, which is not considered part of the list. A line with the single number -1 will mark the end of the file. The example input below shows 3 separate lists. Some lists may not contain any doubles.

Output

The output will consist of one line per input list, containing a count of the items that are double some other item.

Sample Input

1
2
3
4
1 4 3 2 9 7 18 22 0
2 4 8 10 0
7 5 11 13 1 3 0
-1

Sample Output

1
2
3
3
2
0

1.set解析及其用法

头文件 #include < set >

set

set头文件主要包括set和multiset两个容器。他们都是有序集合，不过set存的元素不可重复。

两者内部实现都是红黑树，在使用方法上差别不大，支持的函数基本相同。

声明方式

1
2
3
set<int> s;
multiset<int> t;
set<int>::iterator it;

s与t都是维护int类型数据的有序容器，其中t内的元素可重。迭代器it仅支持++和−−。我们以int类型的数据为例：

s.size()

返回元素个数。

s.empty()

判断set是否为空，为空则是逻辑真，否则就是逻辑假。

s.clear()

清空set。

s.begin()/s.end()

返回set的首迭代器和尾迭代器。第一个元素/最后一个元素

s.insert(x)/s.erase(it/x)

插入一个intint类型的数据，删除一个迭代器或者元素x。如果x已经是在集合中的了，并且是set而不是multiset，那么就不会执行插入操作。时间复杂度为O(log)。如果是multiset则会把所有等于x的元素全部删除，复杂度为O(log+k)，k为元素个数。

s.find(x)

查找等于xx的元素，返回一个迭代器。若不存在，则返回s.end()s.end()。复杂度O(log)O(log)的。

s.lower_bound(x)/s.upper_bound(x)

第一个是找set中大于等于xx的最小的元素，第二个是找set中严格大于xx的最小的元素，以迭代器的形式返回。时间复杂度为O(log)。若不存在，则返回s.end()。

s.count(x)

返回集合中等于x的元素个数。复杂度为O(log+k)，k为元素个数。

迭代器iterator

1. 迭代器(iterator)是一中检查容器内元素并遍历元素的数据类型。

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int>s;
    set<int>::iterator t;//创建一个迭代器t
    int temp;
    cin>>temp;
    while(temp!=-1)
    {
        s.clear();
        while(temp!=0)
        {
            s.insert(temp);
            cin>>temp;
        }
        int c=0;
        for(t=s.begin();t!=s.end();t++)
        {
            if(s.count((*t)*2)!=0)//返回集合中等于（*t*2）的元素个数。
                c++;
        }
        cout<<c<<endl;
        cin>>temp;
    }
    return 0;
}