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個(gè)女孩中取k個(gè)女孩在滿足她們之間的智商差小于一個(gè)MAXK的情況下蘸炸，使她們的顏值和最大躬络。
前面第一眼看到就是DFS+剪枝，時(shí)間復(fù)雜度是O(n!)會(huì)TLE搭儒。
另一種是采取貪心的思想洗鸵，將女孩按智商排序，然后遍歷所有智商差為k的區(qū)間仗嗦，區(qū)間按顏值后取前k個(gè)和sum，然后取所有區(qū)間的sum中最大的一個(gè)甘凭。這種方法的時(shí)間復(fù)雜度是O(n^2*logn)稀拐。
//由于本人比較懶
//這里貼出的是楊同學(xué)的代碼
#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;
}
第三種方法是用線段樹(shù)維護(hù)，建一顆（1丹弱，T）的的線段樹(shù)德撬，維護(hù)區(qū)間內(nèi)的女孩個(gè)數(shù)與顏值和，先將所有女孩按智商排序躲胳，然后遍歷更新到線段樹(shù)中去蜓洪，如果樹(shù)中人數(shù)等于k或者是智商差值大于MAXK，一個(gè)個(gè)減去最左邊的女孩直到滿足要求坯苹，取所有當(dāng)樹(shù)中人數(shù)等于k的顏值和隆檀，也就是MAX{tree[1].sum}。首先一次排序的時(shí)間復(fù)雜度是nlogn粹湃，后面的遍歷每次樹(shù)的更新操作是logT恐仑，時(shí)間復(fù)雜度是nlogT,由于T>n所以總的時(shí)間復(fù)雜度就是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);
}
}
