Codeforces 1373F - Network Coverage （二分）

2021-01-30 06:15

阅读：790

标签：https const ORC ++ 大于等于 math set typedef namespace

Description

思路

如果我们知道某一个站\(b_i\)到对\(a_i\)的贡献是多少，那么就可以用贪心求解（因为这样我们就知道\(b_i\)对\(a_{i+1}\)的贡献，从而知道\(b_{i+1}\)对\(a_{i+1}\)...）。所以可以考虑二分\(b_i\)对\(a_i\)的贡献。

可以把\(b_i\)对\(a_i\)的贡献看作流水，这里\(a_i\)就是容量。

确定了\(b_i\)对\(a_i\)的贡献（设为c）后，有两种结果：

一种是断流（由于\(b_i\)对\(a_i\)贡献太多，导致对\(a_{i+1}\)贡献过少，导致后面断流）；
一种是流一圈后由\(b_{i-1}\)流回\(a_i\)（设流回的量为x）。对于后一种，\(b_i\)对\(a_i\)的贡献每减少1，x至多增加1，因为流一圈过程中可能有地方满流了，继续增加流量，x也不会增加。

所以二分找到使得流回量x>0的最大的c。这个就是边界情况，判断x+c是否大于等于\(a_i\)即可。
这里取\(a_i\)为\(a_1\)。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
#define endl ‘\n‘
#define IOS std::ios::sync_with_stdio(0);
#define FILE freopen("..//data_generator//in.txt","r",stdin),freopen("res.txt","w",stdout)
#define FI freopen("..//data_generator//in.txt","r",stdin)
#define FO freopen("res.txt","w",stdout)
#define pb push_back
#define mp make_pair
#define seteps(N) fixed  n ? i - n : i;
        int cap = arr[p];
        cap = max(cap - out, 0);
        if(cap > brr[p]) return -1;
        out = brr[p] - cap;
    } 
    return out;
}
 
int main() {
    IOS;
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        for(int i = 1; i > arr[i];
        for(int i = 1; i > brr[i];
        int l = 0, r = brr[1];
        while(l = 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }   
        
        if(r = arr[1]) cout

Codeforces 1373F - Network Coverage （二分）

标签：https const ORC ++ 大于等于 math set typedef namespace

原文地址：https://www.cnblogs.com/limil/p/13196715.html

上一篇：【函数分享】每日PHP函数分享(2021-1-29)

下一篇：状态机模式与 ajax 的结合运用

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Codeforces 1373F - Network Coverage （二分）
文章链接：http://soscw.com/essay/49016.html

亲，登录后才可以留言！

Codeforces 1373F - Network Coverage （二分）

Description

思路

评论

热门文章

推荐文章

最新文章

置顶文章