xindoo is
always here

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("%I64d\n", 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;
}
打赏
未经允许不得转载:XINDOO » hdoj 4288coder & cf 85d Sum of Medians
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏