【Hello 2018 D】Too Easy Problems

在这里输入题意

【题解】

可以考虑把所有的题目按照ai排序。
然后顺序考虑最后做出来的题目个数和第i道题目的ai一样。
则1..i-1这些题目就没有用了。
值考虑i..n这些题目就可以了。
显然考虑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;

}

巴特西

【Hello 2018 D】Too Easy Problems

最新文章

热门文章