题目描述
这道题一开始完全想错了。
以为是二分,就先以score排序后按照下标二分,然后check一下,以mid为平均分,以aid分别sort出mid前面和后面的cow。从而得到以mid为均分的最小花费,然后判断是否符合即可。
想法很好,但是,没有考虑到二分性这个根本问题,以score为基准二分的话,如果mid符合条件,不能保证mid以下的所有分数都可以符合aid之和小于f(可以构造出反例)。
所以,正解应该是:
设出cow结构,包含aid,score和rank排名,根据score排序后记录下rank并赋值给cows2.
每次二分时,在cows2中分别记录符合条件的大于mid和小于mid的个数,并分四种情况讨论。
1.如果left<n/2并且right<n/2的话, 表明没有符合条件的答案。
2.如果left<n/2, 说明mid元素太小了, 需要往右移动, 即la= mid;
3.如果right<n/2, 说明mid元素太大了, 需要往左移动, 即lb= mid;
4.如果符合条件, 那么继续贪心, 继续往右找。 即la= mid。
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,c,f;
struct cow{
int score;
int aid;
int rank;
};
cow cows1[N],cows2[N];
bool cmp(cow a,cow b)
{
return a.aid<b.aid;
}
bool cmp1(cow a,cow b)
{
return a.score<b.score;
}
int main()
{
while(scanf("%d %d %d",&n,&c,&f)!=EOF)
{
for(int i=0;i<c;i++)
{
scanf("%d %d",&cows1[i].score,&cows1[i].aid);
}
sort(cows1,cows1+c,cmp1);
for(int i=0;i<c;i++)
{
cows1[i].rank=i;
cows2[i]=cows1[i];
}
sort(cows2,cows2+c,cmp);
int la=0,lb=c,re=-1;
while(lb-la>1)
{
int mid=(la+lb)/2;
int left=0,right=0,total=cows1[mid].aid;
for(int i=0;i<c;i++)
{
if((cows2[i].rank<mid) && (total+cows2[i].aid<=f) && (left<n/2))
{
left++;
total+=cows2[i].aid;
}
if((cows2[i].rank>mid) && (total+cows2[i].aid<=f) &&(right<n/2))
{
right++;
total+=cows2[i].aid;
}
}
if((left<n/2) && (right<n/2))
{
re=-1;
break;
}
else if(left<n/2)
{
la=mid;
}
else if(right<n/2)
{
lb=mid;
}
else
{
re=cows1[mid].score;
la=mid;
}
}
printf("%d\n",re);
}
return 0;
}