[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;
    }
} 

全部评论

相关推荐

给我发了笔试链接,想着等晚上回去做,结果还没做流程就终止了
伟大的小黄鸭在学习:我猜就是笔试几乎没用,就是用来给用人部门拖时间复筛简历的,可能用人部门筛到你简历觉得不合适就提前挂了
投递小鹏汽车等公司10个岗位
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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