AI工具人

# Median

dynamic

##### Max Score: 67

The median of M numbers is defined as the middle number after sorting them in order if M is odd or the average number of the middle 2 numbers (again after sorting) if M is even. 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 numbers in the list.

Example :

For a set of m = 5 numbers, { 9, 2, 8, 4, 1 } the median is the third number in sorted set { 1, 2, 4, 8, 9 } which is 4. Similarly for set of m = 4, { 5, 2, 10, 4 }, the median is the average of second and the third element in the sorted set { 2, 4, 5, 10 }
which is (4+5)/2 = 4.5

Input:

The first line is an integer n indicates the number of operations. Each of the next n lines is either “a x” or “r x” which indicates the operation is add or remove.

Output:

For each operation: 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. (if the result is an integer DO NOT output decimal point. And if the result is a double number , DO NOT output trailing 0s.)

Constraints:

0 < n <= 100,000

For each “a x” or “r x”, x will always be an integer which will fit in 32 bit signed integer.

Sample Input:

7
r 1
a 1
a 2
a 1
r 1
r 2
r 1

Sample Output:

Wrong!
1
1.5
1
1.5
1
Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty you have to print “Wrong!” ( quotes are for clarity ).

我这里使用了stl里的multiset（因为可能有重复的元素，所以不能使用set），set可以以O(logn)的时间复杂度进行插入和删除，而且在插入删除的过程中也会维持有序，这样我们就不需要额外的排序工作了，这无疑又节省了时间。但是，set好像不能随机访问，至少我还没找到随机访问的方法（如果有找到告诉我一声），所以我只能通过迭代器遍历访问最中间的元素了，可能是因为这个原因，后面几组测试样例都超时了，下面看我解题代码，我只能说我只有第一组测试过了，后面的错误和超时，求批评指正。

#include <stdio.h>
#include <set>;
using namespace std;

multiset<int> s;                                 //不能用set请回看上文

int main()
{
int n, l;
while (scanf("%d",&n) != EOF)
{
s.clear();
l = 0;
char op;
int x;
while (n--)
{
int f = 1;
getchar();
scanf("%c %d",&op,&x);
multiset<int>::iterator it;            //迭代器指针，虽然不懂，但是就这么用了
if (op == 'r')
{
if (s.count(x) == 0)
{
puts("Wrong!");
f = 0;
}
else
{
it = s.find(x);
s.erase(it);
/*这里要解释一下，为什么不直接使用s.erase(x)呢！！因为x可能有多个值，
这样会将所有的x都删除的*/
l--;
if (!l)
{
f = 0;
puts("Wrong!");
}
}
}
else
{
s.insert(x);
l++;
}
if (f)
{
it = s.begin();
if (l == 1)
{
printf("%d\n",*it);
continue;
}
for (int i = 1; i < l/2; i++)
it++;
if (l%2 == 1)
{
it++;
printf("%d\n",*it);
}
else
{
float ans = (float)*it;
it++;
ans += (float)*it;
printf("%g\n",ans / 2);
}
}
}
}
return 0;
}

这道题的关键在于，不能用int，因为两个int相加可能会越界！因为这个WA了好多遍。所以改用long long。

/* Sample program illustrating input and output */

#include<iostream>
#include<math.h>
using namespace std;

long long a[100001];

void getMedian(int size)
{
double sum = 0;
if (size % 2 == 0)
{
sum = (double(a[size/2]) + double(a[size/2-1])) / 2;
}
else
sum = a[size/2];
if (ceil(sum) == sum)
printf("%.0lf\n", sum);
else
printf("%.1lf\n", sum);
}

int findAndRemove(long long key, int size)
{
int begin = 0;
int end = size - 1;
while(begin <= end)
{
int mid = (begin+end)/2;
if (a[mid] < key)
begin = mid + 1;
else if (a[mid] > key)
end = mid - 1;
else
{
int i = mid;
while(i < size - 1)
{
a[i] = a[i+1];
i++;
}
return true;
}
}
return false;
}

int main(){
int currentSize = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
char operation;
long long value;
cin >> operation >> value;
if (operation == 'r')
{
if (currentSize <= 0)
cout << "Wrong!" << endl;
else
{
if (findAndRemove(value, currentSize))
{
currentSize--;
if (currentSize == 0)
cout << "Wrong!" << endl;
else
getMedian(currentSize);
}
else
cout << "Wrong!" << endl;
}
}
else
{
if (currentSize == 0)
a[0] = value;
else
{
int begin = 0;
int end = currentSize - 1;
while(begin <= end)
{
int mid = (begin+end) / 2;
if (a[mid] < value)
begin = mid + 1;
else
end = mid - 1;
}
int i = currentSize;
while(i> begin)
{
a[i] = a[i-1];
i--;
}
a[begin] = value;
}
currentSize++;
getMedian(currentSize);
}
}
}