2015 년 JXNUACS 알고리즘 그룹 겨울방학 첫 번 째 주 경기 1005 수 는 희소 성 이 비싸다

드물다.
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65535/2400K (Java/Other)
Total Submission(s) : 30   Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
n 개 수 를 제시 합 니 다.이 n 개 수 중 일 부 는 모두 1 번 나 타 났 고,일 부 는 모두 2 번 나 타 났 으 며,일 부 는 모두 3 번 나 타 났 습 니 다.어떤 수 는 n 번 나 타 났 습 니 다.
물건 은 희귀 하기 때문에 현재 작은 KD 는 한 번 나 온 숫자 에 만 관심 이 있 습 니 다.프로그램 을 만들어 서 찾 아 주 고 오름차 순 으로 출력 해 주세요.
Input
첫 번 째 줄 에는 정수 t 가 있 는데 모두 t 조 테스트 데이터 가 있 음 을 대표 합 니 다.
각 조 의 테스트 데 이 터 는 두 줄 이 있 고 첫 번 째 줄 에 n 을 입력 하면 n 개의 수가 있 음 을 나타 내 며 n 의 수치 범 위 는[1,10^6]이다.
두 번 째 줄 에는 n 개의 숫자 가 있다.각 숫자의 크기 범위[1,10^6].
Output
각 그룹의 데이터 에 대응 하 는 출력 은 두 줄 이 있다.
첫 번 째 줄 은 정 수 를 출력 하여 한 번 나타 난 수의 개 수 를 나타 낸다.
두 번 째 줄 은 오름차 순 으로 출력 횟수 가 한 번 인 숫자 로 두 숫자 사 이 를 빈 칸 으로 분리 합 니 다.
Sample Input

3
5
1 2 2 3 3
7
1 2 2 3 4 4 2
2
2 2

Sample Output

1
1
2
1 3
0

Author
JXNU_WY 
이 문제 의 산법 은 모두 쉽게 생각 할 수 있 지만,이것 은 내 가 고찰 해 야 할 곳 이 아니다.이 문 제 는 분석 능력 을 시험 한 것 이다.
우선 각종 데이터 형식 이 차지 하 는 메모리 크기 를 한눈 에 알 아야 한다.제목 이 메모리 에 걸 렸 습 니 다.한정 메모 리 는 2 천 400 K 다.
특히 bool 형식 은 자바 에서 한 자 리 를 차지 하고 c 와 c++는 바이트 입 니 다.
이 문제 에서 성형 배열 을 열 면 총 바이트 를 계산 해 볼 수 있 습 니 다.
4*1000000/1024=3906K
분명히 메모리 초과.
이 문제 에서 두 개의 bool 배열 을 열 때 사용 하 는 총 바이트 는:
2*1000000/1024=1953K
프로그램 에 있 는 다른 변 수 를 더 하면 초 메모리 입 니 다.
그럼 또 하나의 배열 이 있 습 니 다.그것 이 바로 문자 배열 입 니 다.
문자 배열 의 모든 요 소 는 하나의 바이트 를 차지 하기 때문에 128 가지 상태 가 있 기 때문에 하 나 를 열 면 충분 합 니 다.
총 바이트:976 K
게다가 프로그램 에서 다른 변수 가 차지 하 는 메모리 도 여유 가 있다.
다음은 C++의 참고 코드 입 니 다.

#include
#include
#include
#include
using namespace std;
const int L=1000005;
char b[L];
int main()
{
    int n,a,t;
    cin.sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        bool flag=false;
        memset(b,0,sizeof(b));
        int sum=0;
        for(int i=0;i>a;
            if(b[a]==0) b[a]=1,sum++;
            else  if(b[a]==1) b[a]=2,sum--;
        }
        cout<