hdoj 4288coder & cf 85d Sum of Medians

题目链接

   这两个题目是一样的，大概题意是有3个操作 add x， 在集合中加入x， del x 是删除x， sum 是求出由小到大排序后所有下标mod5等于3的数的和。

   这个在hdoj上面，这个题给的时间比较多10s，我用了stl 里的vector和 lower_bound， lower_bound 它的作用是返回不小于x的第一个数的位置，这样我们每次插入后就能保证他有序。 最终耗时6234MS，而这种方法在codeforces上超时了，cf只给了3000ms，这道题的标准做法是用线段树。

 先给出stl的做法

复制代码//2013-05-18-20.17 // hdoj 4288 cf 85d #include <stdio.h> #include <algorithm> #include <vector> using namespace std; char op[5]; vector<int> v; int main() { int n, x; while (scanf("%d", &n) != EOF) { v.clear(); while (n--) { scanf("%s", op); if (op[0] == 's') { __int64 ans = 0; for (int i = 2; i < v.size(); i += 5) ans += v[i]; printf("%I64dn", ans); } else { scanf("%d", &x); if (op[0] == 'a') v.insert(lower_bound(v.begin(), v.end(), x), x); else v.erase(lower_bound(v.begin(), v.end(), x)); } } } return 0; }

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
30
31
32
33
34
35
36
37
//2013-05-18-20.17
// hdoj 4288 cf 85d
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
char op[5];
vector<int> v;
int main()
{
int n, x;
while (scanf("%d", &n) != EOF)
{
v.clear();
while (n--)
{
scanf("%s", op);
if (op[0] == 's')
{
__int64 ans = 0;
for (int i = 2; i < v.size(); i += 5)
ans += v[i];
printf("%I64dn", ans);
}
else
{
scanf("%d", &x);
if (op[0] == 'a')
v.insert(lower_bound(v.begin(), v.end(), x), x);
else
v.erase(lower_bound(v.begin(), v.end(), x));
}
}
}
return 0;
}