AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列）

90 阅读 0 评论 60 点赞

我是靠谱客的博主粗暴御姐，最近开发中收集的这篇文章主要介绍AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Statement

You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is Ai, and the i-th element in B is Bi.

Tozan and Gezan repeats the following sequence of operations:

If A and B are equal sequences, terminate the process.
Otherwise, first Tozan chooses a positive element in A and decrease it by 1.
Then, Gezan chooses a positive element in B and decrease it by 1.
Then, give one candy to Takahashi, their pet.

Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.

Constraints

1≤N≤2×105
0≤Ai,Bi≤109(1≤i≤N)
The sums of the elements in A and B are equal.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A1 B1
:
AN BN

Output

Print the number of candies given to Takahashi when both Tozan and Gezan perform the operations optimally.

Sample Input 1

Copy

2
1 2
3 2

Sample Output 1

Copy

When both Tozan and Gezan perform the operations optimally, the process will proceed as follows:

Tozan decreases A1 by 1.
Gezan decreases B1 by 1.
One candy is given to Takahashi.
Tozan decreases A2 by 1.
Gezan decreases B1 by 1.
One candy is given to Takahashi.
As A and B are equal, the process is terminated.

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

1
1 1

Sample Output 3

Copy

题意：给出A B 2个序列，他们的序列总和相同，2个人T和G，双方轮流选择序列中一个正整数，进行减一，

T想尽可能的使步数大，G想尽可能的使步数小，计算使得2个序列完全相同的步数

当所有的Bi=Ai的时候输出0

G:为了使得步数尽可能的小，当Bi>Ai的时候只要减少Bi即可，当Bi<Ai的时候，不动即可

T:为了使得步数尽可能的大，当Bi>Ai的时候，Ai必定最后为0，当Bi<Ai的时候，记录最小的Bi为Bk（k为符合条件的最小值的下标），让G误以为所有的A都是要趋向于Bk，实则是为了变为0，除非T不得不移动Ak（也就是其他的A都为0）

综上得：结果为sum-minb

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main()
{
	int t;
	cin>>t;
	ll sum=0,a,b,minb=INF,flag=0;
	while(t--){
        cin>>a>>b;
        sum+=b;
        if(b<a&&minb>b)
            minb=b;
        if(b!=a)
            flag=1;
	}
 
	if(flag==1)
        cout<<sum-minb<<endl;
    else
        cout<<0<<endl;
}

最后

以上就是粗暴御姐为你收集整理的AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列）的全部内容，希望文章能够帮你解决AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：ACM_数字处理与数论
浏览次数：90 次浏览
发布日期：2023-09-03 04:55:23
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzo_10_fx_12__23__26_2.html

AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列）

概述

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

最后

评论列表共有 0 条评论

发表评论取消回复

AtCoder Regular Contest 094 E - Tozan and Gezan （博弈论 2个和相同序列双方轮流减一得最后完全相同序列）

概述

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复