【Hello 2018 D】Too Easy Problems

在这里输入题意

【题解】

可以考虑把所有的题目按照ai排序。然后顺序考虑最后做出来的题目个数和第i道题目的ai一样。则1..i-1这些题目就没有用了。值考虑i..n这些题目就可以了。显然考虑ti最小的若干项。使得它们的时间和<=T然后不超过a[i] 可以二分选择了前mid小的题目。看看时间和以及题目个数是否满足要求。满足的话就更大一点。然后记录是从哪个地方开始的最小ans个题目。最后模拟输出就好了。 (可以用树状数组来加速获取前mid时间以及个数和。 (另开一个数组,记录第i道题目如果以ti排序排在第几。 (以那个,建立树状数组

我这个做法太麻烦了。。

另解1
我这种做法其实可以做得更好一点:
即枚举题目个数i从n递减到1
然后在一个集合中维护ai>=i的题目(只要枚举到第i个的时候,把ai==i的加入set里面就好了),然后保证集合的大小为i就可以了。
->如果大于k了,那么就把ti最大的那几个删掉,直到集合的大小为k
维护集合里面的题目的和就好。

另解2
二分最后的分数。
显然如果分数mid可以得到的话。
那么分数mid-1肯定也可以得到。
可以看出来有单调性。

【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5;

struct BI {
	ll a[N + 10],b[N+10];

	int lowbit(int x) {
		return x&(-x);
	}

	void add(int x,int y) {
		while (x <= N) {
			a[x] += y;
			x += lowbit(x);
		}
	}

	void add2(int x,int y) {
		while (x <= N) {
			b[x] += y;
			x += lowbit(x);
		}
	}


	ll sum(int x) {
		int now = 0;
		while (x > 0) {
			now += a[x];
			x -= lowbit(x);
		}
		return now;
	}


	int sum2(int x) {
		int now = 0;
		while (x > 0) {
			now += b[x];
			x -= lowbit(x);
		}
		return now;
	}

	ll get_sum(int l, int r) {
		return sum(r) - sum(l - 1);
	}

	int get_sum2(int l, int r) {
		return sum2(r) - sum2(l - 1);
	}

}B;

struct abc{
    int a,t,idx;
};

bool cmp(abc a,abc b){
    return a.a<b.a;
}

bool cmp2(abc a,abc b){
    return a.t<b.t;
}

abc a[N+10],b[N+10];
int should[N+10];
multiset< int > myset;
bool bo[N+10];
int n,t;

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> t;
    for (int i = 1;i <= n;i++){
        cin >> a[i].a >> a[i].t;
        a[i].idx = i;
    }
    for (int i = 1;i <= n;i++) myset.insert(a[i].t);

    sort(a+1,a+1+n,cmp);

    for (int i = 1;i <= n;i++) b[i] = a[i];
    sort(b+1,b+1+n,cmp2);
    for (int i = 1;i <= n;i++){
        should[b[i].idx] = i;
        B.add(i,b[i].t);
        B.add2(i,1);
    }


    int ans = 0,index = -1;
    for (int i = 1;i <= n;i++){
        int num = a[i].a;
        ll now = 0;
        int j = 0;
        int l = 1,r = n,temp = -1,temptot;
        while (l <= r){
            int mid = (l+r)>>1;
            int cnt = B.get_sum2(1,mid);
            ll tot = B.get_sum(1,mid);
            if (cnt<=num && tot<=t){
                temptot = cnt;
                l = mid+1;
                temp = mid;
            }else{
                r = mid - 1;
            }
        }

        if (temp!=-1){
            if (temptot>ans) {
                ans = temptot;
                index = i;
            }
        }


        j = i;
        int tt = should[a[i].idx];
        B.add2(tt,-1);
        B.add(tt,-a[i].t);
        bo[a[i].idx] = true;
        while (j+1<=n && a[j+1].a==a[i].a) {
                j++;
                bo[a[j].idx] = true;
                int tt = should[a[j].idx];
                B.add2(tt,-1);
                B.add(tt,-a[j].t);
        }
        i = j;
    }
    cout << ans << endl;
    cout << ans << endl;
    if (index!=-1){
        sort(a+index,a+1+n,cmp2);
        for (int i = index;i <= index+ans-1;i++)
                cout <<a[i].idx<<' ';
    }
	return 0;
}