[Algorithm Elementary][NOIP2012]借教室

[NOIP2012]借教室

https://ac.nowcoder.com/acm/contest/22353/H

Thinking Process

Use binary search and testify every value.
Assume you have known answer and check answer wheather right. If not right, how to update answer and testify it again until you verify its correctness.
This is the process of this excersize.
We can use difference to transfer interval update to point update in testify code. And finally sum them up. If one value in process less than zero return false.

Code

#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;

struct ty{
    ll d, s, j;    
}a[1000010];
ll b[1000010];
ll diff[1000010];
ll n, m;
bool check(ll x) {
    memset(diff, 0, sizeof(diff));
    for(ll i = 1;  i <= n; i ++) diff[i] = b[i] - b[i - 1];
    for(ll i = 1;  i <= x;i ++) {
        diff[a[i].s] -= a[i].d;
        diff[a[i].j + 1] += a[i].d;
    } 
    ll res = 0;
    for(ll i = 1; i <= n; i ++){
        res += diff[i];
        if(res < 0) return false;
    }
    return true;
} 
int main() {
    cin >> n >> m;
    for(ll i = 1; i <= n ; i++ ) cin >> b[i];
    for(ll i = 1; i <= m ; i ++) {
        cin >> a[i].d >> a[i].s >> a[i].j;
    }
    ll l = 1, r = 1e6 + 10;
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    } 
    
    if(check(l)) cout << 0 << endl;
    else {
        cout << "-1" << endl << l;
    }
} 

全部评论

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
下北澤大天使:你是我见过最美的牛客女孩😍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务