Codeforces Round #377 (Div. 2) D. Exams 二分+贪心 or 纯贪心水过

Source

Codeforces Round #377 (Div. 2)

My Solution

二分+贪心 or 纯贪心水过

/*!!!!!!

1、纯贪心水过，事实上并不对

比赛的时候是纯贪心水过了，后来经过同学和热心读者们的提醒，发现纯贪心是水过去的，事实上并不对，抱歉

首先a[maxn] 进行排序，

然后扫一遍d[maxn]， 对于每次 d[i] == 0，则cnt++;

d[i] >= 0， 则如果 cnt >= a[ptr] 则 cnt -= a[ptr]， ptr++;

否则 cnt++;

这里要注意  He can mix the order of preparation for exams in any way. 这句话

所以优先使用小的a[i]，因为当cnt足够的时候， 大的a[i]能用的时候，小的a[i]也能用，而如果只能小的a[i]用的时候 大的a[i]却不能用，

要尽可能少的天数，所以当遇到d[i] > 0 时就先把小的用掉，因为这个时候大的可能不能用， 尽可能把当前遇到的d[i] > 0 的 i用掉( 用来考试),

//因为d[i] == 0 只能复习，而d[i] > 0，可以2种用途，优先把d[i]用来考试，则对后面可以安排的更自如。

复杂度 O(n)

*/

2、二分+贪心

二分右端点，然后check [0, x) 能不能满足条件，然后可以则 r = x, 否则l = x;

关于check()函数，从右端点往左扫一遍，只留下最靠右的相同d[j]值(把这些处理后的数据放到一个新的数组b[nmaxn]里)，然后从左往右贪/*贪心的策略就是"1、纯贪心水过的策略"*/

最后的r就是答案了，

当 r == l 是 可能是没有答案也可能答案为n，所以对于这种情况再check(n)一次

复杂度 O(nlogn)

1、纯贪心水过，事实上并不对

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

LL d[maxn], a[maxn];

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

    LL n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){ cin >> d[i];
    }
    for(int i = 0; i < m; i++){ cin >> a[i];
    }

    sort(a, a + m);
    int cnt = 0, ptr = 0, ans = 0;
    for(int i = 0; i < n; i++){
        if(ptr == m) {ans = i; break;}
        if(d[i] == 0) cnt++;
        else{
            if(cnt < a[ptr]){
                cnt++;
            }
            else{
                cnt -= a[ptr];
                ptr++;
            }
        }
    }

    if(ptr != m) cout << -1 << endl;
    else{
        if(ans == 0) cout << n << endl; //
        else cout << ans << endl;
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

2、二分+贪心

#include 
#include 
#include 
#include 

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx