MM编程俱乐部 (线段树）

MM编程俱乐部

ACM is popular in HDU. Many girls want to learn more about programming skills in ACM. As one of assistances of Lcy, Yifenfei is now busy preparing a new club called “MM Programming Club”. Of Course, He will be the leader of the club, and teach these girls patiently. After the news posted around the campus, as many as N girls are determined to take part in the club. However, the numbers of members are limited; Yifenfei will only select K of them. It is quite a difficult problem. Here is a list of all information about N girls. Each of them has intelligence value and prettiness value. He also wants these K members such that the difference of intelligence between any two of them must not be greater than MAXK (If K = 1, the difference is zero). Now he wants to maximize the Sum of these K girls’ prettiness value.

Input

Many test case, please process to end of file. Each test first contains three integers N(1 <= N <= 200), K(1 <= K <= N), MAXK(1 <= MAXK <= 500). Then N lines follow. Each line contains two integers S, T (1 <= S, T <= 500). S represents the intelligence value, and T represents the prettiness value.

Output

If he can’t succeed in selecting K girls, print “-1”. Otherwise, Print the maximum the Sum of these K girls’ prettiness value.

Sample Input

2 1 0
1 2
2 3
2 2 0
1 2
2 3
2 2 1
1 2
2 3

Sample Output

3
-1
5

题目的大概意思是在n个女孩中取k个女孩在满足她们之间的智商差小于一个MAXK的情况下，使她们的颜值和最大。
前面第一眼看到就是DFS+剪枝，时间复杂度是O(n!)会TLE。
另一种是采取贪心的思想，将女孩按智商排序，然后遍历所有智商差为k的区间，区间按颜值后取前k个和sum，然后取所有区间的sum中最大的一个。这种方法的时间复杂度是O(n^2*logn)。

//由于本人比较懒
//这里贴出的是杨同学的代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=10000+5;
struct node{
    int w,v;
}stu[maxn];
bool cmp1(node x,node y)
{
    return x.w<y.w;
}
bool cmp2(node x,node y)
{
    return x.v>y.v;
}
int n,k,limit,res,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>k>>limit)
    {
        res=-1;
        for(int i=1;i<=n;i++)
        cin>>stu[i].w>>stu[i].v;
        sort(stu+1,stu+n+1,cmp1);
        for(int i=1;i<=n;i++)
        {
            ans=stu[i].v;
            int w=stu[i].w;
            vector<node> tmp;
            for(int j=i+1;stu[j].w-w<=limit&&j<=n;j++)
                tmp.push_back(stu[j]);
            if(tmp.size()<k-1) continue;
            sort(tmp.begin(),tmp.end(),cmp2);
            for(int m=0;m<k-1;m++)
                ans+=tmp[m].v;
            res=max(res,ans);
        }
        cout<<res<<endl;
    }
    return 0;
}

第三种方法是用线段树维护，建一颗（1，T）的的线段树，维护区间内的女孩个数与颜值和，先将所有女孩按智商排序，然后遍历更新到线段树中去，如果树中人数等于k或者是智商差值大于MAXK，一个个减去最左边的女孩直到满足要求，取所有当树中人数等于k的颜值和，也就是MAX{tree[1].sum}。首先一次排序的时间复杂度是nlogn，后面的遍历每次树的更新操作是logT，时间复杂度是nlogT,由于T>n所以总的时间复杂度就是nlogT。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
    int s,t;
    bool operator < (const node & e) const {
            return s<e.s;
        }
};
struct seg{
    int l,r,mid;
    int s;
    int num;
};
seg tree[505<<2];
node n_[205];
int ri;
void build(int k,int l,int r){
    tree[k].l=l;
    tree[k].r=r;
    tree[k].mid=(l+r)>>1;
    tree[k].s=tree[k].num=0;
    if(l==r)return;
    build(k<<1,l,tree[k].mid);
    build(k<<1|1,tree[k].mid+1,r);
}
void pushup(int k){
    tree[k].s=tree[k<<1].s+tree[k<<1|1].s;
}
void add(int k,int x){
    tree[k].num++;
    if(tree[k].l==tree[k].r){
        tree[k].s+=x;
        return;
    }
    if(x<=tree[k].mid)add(k<<1,x);
    else add(k<<1|1,x);
    pushup(k);
}
void sub(int k,int x){
    tree[k].num--;
    if(tree[k].l==tree[k].r){
        tree[k].s-=x;
        return;
    }
    if(x<=tree[k].mid)sub(k<<1,x);
    else sub(k<<1|1,x);
    pushup(k);
}
int sum(int k,int x){
   
    if(!x)return 0;
    if(tree[k].l==tree[k].r){
        return x*tree[k].l;
    }
    if(x<=tree[k<<1|1].num)return sum(k<<1|1,x);
    else return sum(k<<1,x-tree[k<<1|1].num)+tree[k<<1|1].s;
}
int main(){
    int n,k,d;
    while (scanf("%d%d%d",&n,&k,&d)!=EOF){
       for(int i=1;i<=n;i++){
          scanf("%d%d",&n_[i].s,&n_[i].t);
       }
       sort(n_+1,n_+1+n);
        ri=1;
        build(1,1,500);
        int res=-1;
        for(int i=1;i<=n;i++){
            add(1,n_[i].t);
            while (ri<=i&&n_[i].s-n_[ri].s>d){
                sub(1,n_[ri].t);
                ri++;
            }
            if(tree[1].num>=k){
                res=max(res,sum(1,k));
            }
        }
        printf("%d\n",res);
    }
}