Codeforces Hello 2018 D. Too Easy Problems 二分+贪心

My Solution

题意：有m个题目，每个题目有个需要花费的时间ti，以及ai，表示只要最终过题数不超过ai这个题才count。求最大的过题数以及过了哪些题，多种答案则输出任一答案。

二分+贪心

首先把题目按照ti的为优先级排序，时间少的在前面。

然后二分答案，mid表示最终的过题数，check的时候，维护剩余的时间tmp，用cnt表示已选的题目数量，

对于题目从左向右扫，每次如果该题的ai<= mid 则 tmp -= ti，当tmp >= 0是cnt++，然后tmp <= 0时break。

之后cnt >= mid则返回真，否则返回假。

最后得出ans后再按照check的方法再跑一边就可以得到具体选的题目。

#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
const int MAXN = 2e5 + 8;

struct p{
    int t, a, ind;
} ta[MAXN];
inline bool cmp(const p &a, const p &b){
    return a.t < b.t;
}


LL n, time, tmp;
inline bool check(LL mid){
    int i, cnt = 0;
    tmp = time;
    for(i = 0; i < n; i++){ if(ta[i].a >= mid){
            tmp -= ta[i].t;
            if(tmp >= 0) cnt++;
            else break;
        }
    }
    if(cnt >= mid) return true;
    else return false;

}

vector ansset;
inline bool findans(LL mid){
    int i, cnt = 0;
    tmp = time;
    for(i = 0; i < n; i++){ if(ta[i].a >= mid){
            tmp -= ta[i].t;
            if(tmp >= 0) cnt++, ansset.push_back(ta[i].ind);
            else break;
        }
        if(cnt == mid) break;
    }
}

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL i, a, t, ans = 0;
    cin >> n >> time;
    for(i = 0; i < n; i++){ cin >> ta[i].a >> ta[i].t;
        ta[i].ind = i+1;

    }
    sort(ta, ta + n, cmp);
    LL l = 0, r = n + 1, mid;
    while(l + 1 < r){ mid = (l + r) >> 1;
        if(check(mid)){
            ans = mid;
            l = mid;
        }
        else r = mid;
    }

    cout << ans << endl;
    cout << ans << endl;
    findans(ans);
    for(i = 0; i < ans; i++){
        if(i != 0) cout << " ";
        cout << ansset[i];
    }
    cout << endl;


    #ifdef LOCAL
    ansset.clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

                                                                                                                                             ------from ProLightsfx