CodeForces - 913D

最多做多少题，而且那道题i要总数不超过a[i]才能得分。

二分答案，就好判断了。

先按a[i]来排序问题，大的放前面，那对于最多做mid的时候，就从前到后吧a[i]<=mid的放进B，然后吧B按照耗时排序，有限取最小的。

然而我们发现复杂度最坏是nlognlogn。虽然我还是过了

然而，今天学长讲题解后发现，直接对a按照耗时排序，然后二分一个答案后直接对a从前往后吧符合的进行相加然后与m判断大小，复杂度就是nlogn了。

如果数据范围再大点再加上a[i]都大于n的话我这个最坏复杂度直接就GG了。

前几篇全是这个问题，做水题的姿势还是需要学习一个。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxl 200010

using namespace std;

int n,m,cnt,k;
struct pro
{
	int d,t,ind;
}a[maxl],b[maxl];
int ans[maxl];

bool cmp(const pro &x,const pro &y)
{
	if(x.d==y.d)
		return x.t<y.t;
	else
		return x.d>y.d;
}

inline void prework()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].d,&a[i].t);
		a[i].ind=i;
	}
	sort(a+1,a+1+n,cmp);
}

bool cmp2(const pro &x,const pro &y)
{
	return x.t<y.t;
}

inline bool jug(int mid)
{
	cnt=0;
	for(int i=1;i<=n;i++)
	if(a[i].d>=mid)
		b[++cnt]=a[i];
	else
		break;
	sort(b+1,b+1+cnt,cmp2);
	int sum=0;
	if(cnt<mid)
		return false;
	for(int i=1;i<=mid;i++)
	{
		sum+=b[i].t;
		if(sum>m)
			return false;
	}
	return true;
}

inline void mainwork()
{
	int l=0,r=n,mid;
	while(l+1<r)
	{
		mid=(l+r)>>1;
		if(jug(mid))
			l=mid;
		else
			r=mid;
	}
	if(jug(r))
		k=r;
	else
		k=r-1;
}

inline void print()
{
	int mid=k;
	printf("%d\n%d\n",k,k);
	cnt=0;
	for(int i=1;i<=n;i++)
	if(a[i].d>=mid)
		b[++cnt]=a[i];
	sort(b+1,b+1+cnt,cmp2);
	for(int i=1;i<=k;i++)
		printf("%d ",b[i].ind);
}

int main()
{
	prework();
	mainwork();
	print();
	return 0;
}