本文共 5164 字，大约阅读时间需要 17 分钟。

Description

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

分析

然而，并没有收到很好的答复，也是第一次去参与论坛，然后默认邀请了一部人帮忙解答，结果。。。

好在，身边还是有一些算法能力比较强的同学，提出来了解题思路

第一种方法：（dfs）

对每个点进行搜索，过于暴力，会超时

第二种方法：（贪心）

采用贪心思想，先按照智力从小到大排序，可以这样理解，最优解中肯定有一个人智力最小，所以我们轮流让每个人做智力最小的人，肯定能找到最优解

时间复杂度：O(n^2 logn)

第三种方法：（线段树维护）

这里引用了我队友的“简书”了，附上地址：

建一颗（1，T）的的线段树，维护区间内的女孩个数与颜值和，先将所有女孩按智商排序，然后遍历更新到线段树中去，如果树中人数等于k或者是智商差值大于MAXK，一个个减去最左边的女孩直到满足要求，取所有当树中人数等于k的颜值和，也就是MAX{tree[1].sum}。

首先一次排序的时间复杂度是nlogn，后面的遍历每次树的更新操作是logT，时间复杂度是nlogT,由于T>n所以总的时间复杂度就是nlogT。

时间复杂度：O(nlogT)

dfs代码 显然TLE

---

#include
   
    #include
    
     #include
     
      #include
      
       #define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=600+5;struct node{
       int w,v;}stu[maxn];int n,k,limit,res,cnt,ans;int vis[maxn];bool is_OK(int t){
       for(int i=1;i<=n;i++)    {
           if(vis[i])        {
               if(abs(stu[i].w-stu[t].w)>limit)                return false;        }    }    return true;}void dfs(int t){
      if(k==cnt)    res=max(res,ans);   if(t>n)    return;   for(int i=1;i<=n;i++)   {
          if(!vis[i])       {
              if(is_OK(i))           {
                  vis[i]=1;               ++cnt;               ans+=stu[i].v;               dfs(t+1);               ans-=stu[i].v;               --cnt;               vis[i]=0;           }       }   }}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n>>k>>limit)    {
           res=0,cnt=0,ans=0;        mst(vis,0);        for(int i=1;i<=n;i++)        {
               cin>>stu[i].w>>stu[i].v;        }        dfs(1);        if(res)        cout<
       
        <
       
      
     
    
   

ycy暴力贪心

---

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #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.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++) //判断条件i<=n也可以写成i<=n-k+1 { //因为我们每次都要再拿k-1个人，n-k+1 //后面已经不能满足k-1个人了 ans=stu[i].v; int w=stu[i].w; vector
         
           tmp; for(int j=i+1;stu[j].w-w<=limit&&j<=n;j++) tmp.push_back(stu[j]); if(tmp.size()
         
        
       
      
     
    
   

miaos线段树维护

---

至于线段树这块，我还没有去了解，或者说最近稍微比较懒散吧，这里我先提供我的队友miaos的代码，供大家参考，待我了解了我就再重新写一篇博客，把这个当做例子

#include
   
    #include
    
     #include
     
      using namespace std;struct node{
       int s,t;    bool operator < (const node & e) const {
               return s
      
       >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;}void debug(){
       for(int i=0;i<1000;i++){
           cout<
       
        <<" ";    }    cout<
        
         d) { //cout<<"n_[ri].t: "<
         
          <
          
           =k){ res=max(res,sum(1,k)); } } // debug(); printf("%d\n",res); } }
          
         
        
       
      
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/97957102 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！