程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3612 Median (multiset)

ZOJ 3612 Median (multiset)

編輯:C++入門知識

Median

Time Limit: 5 Seconds Memory Limit: 65536 KB

The median of m numbers is after sorting them in order, the middle one number of them if m is even or the average number of the middle 2 numbers if m is odd. You have an empty number list at first. Then you can add or remove some number from the list.

For each add or remove operation, output the median of the number in the list please.

Input

This problem has several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases. The first line of each test case is an integer n(0<n<=10000) indicates the number of operations. Each of the next n lines is either "add x" or "remove x"(-231<=x<231) indicates the operation.

Output

For each operation of one test case: If the operation is add output the median after adding x in a single line. If the operation is remove and the number x is not in the list, output "Wrong!" in a single line. If the operation is remove and the number x is in the list, output the median after deleting x in a single line, however the list is empty output "Empty!".

Sample Input

2
7
remove 1
add 1
add 2
add 1
remove 1
remove 2
remove 1
3
add -2
remove -2
add -1

Sample Output

Wrong!
1
1.5
1
1.5
1
Empty!
-2
Empty!
-1

Hint

if the result is an integer DO NOT output decimal point. And if the result is a double number , DO NOT output trailing 0s.



題意:給你一個容器,每次執行add或者remove操作,當容器不為空時,輸出容器中元素的中位數;如果為空,輸出Empty!或者Wrong!

分析:比賽時也想到了用multiset,但是刪除時會把所有相同的元素一起刪掉,沒想到用指針指向要刪除的元素。這題還可以用樹狀數組或者線段樹來做。


#include
#include
#include
#include
using namespace std;

multiset ms;
multiset::iterator it; //指向要刪除的元素的位置
multiset::iterator it1; //記錄中位數的位置
multiset::iterator it2; //輔助迭代器

int main()
{
    int t, n, i;
    char op[20];
    int a;
    scanf("%d",&t);
    while(t--)
    {
        ms.clear();
        scanf("%d",&n);
        for(i = 0; i < n; i++)
        {
            scanf("%s%d",op, &a);
            if(!strcmp(op, "add"))
            {
                ms.insert(a);
                if(ms.size() == 1)
                    it1 = ms.begin();
                else
                {
                    if((ms.size()&1) && a >= *it1) it1++;
                    else if((ms.size() % 2 == 0 && a < *it1)) it1--;
                }
            }
            else
            {
                it = ms.find(a);
                if(it == ms.end())
                {
                    printf("Wrong!\n");
                    continue;
                }
                else
                {
                    if(*it1 == a)
                    {
                        it = it1;
                        if(ms.size() % 2 == 0)
                            it1++;
                        else
                            it1--;
                    }
                    else
                    {
                        if((ms.size()&1) && a >= *it1) it1--;
                        else if(ms.size() % 2 == 0 && a < *it1) it1++;
                    }
                    ms.erase(it);
                }
            }
            int s = ms.size();
            if(s == 0) printf("Empty!\n");
            else
            {
                if(s&1)
                    printf("%d\n",*it1);
                else
                {
                    it2 = it1;
                    it2++;
                    long long ans = (long long)*it1 + (long long)*it2;
                    if(ans % 2 == 0)
                        printf("%lld\n",ans/2);
                    else
                        printf("%.1lf\n",ans/2.0);
                }
            }
        }
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved