[ABC365C] Transportation Expenses

[ABC365C] Transportation Expenses

题面翻译

【题目描述】

有 N N N个人参加某项活动，第 i i i人的交通费用为 A i A_i Ai​日元

活动组织者Takahashi决定为交通补贴设定最高限额 x x x。第 i i i人的补贴将为 m i n ( x , A i ) min(x,A_i) min(x,Ai​)日元。这里， x x x必须是非负整数。

假设Takahashi的预算为 M M M日元，并且他希望所有 N N N人的交通补贴总额最多为 M M M日元，那么补贴限额 x x x的最大可能值为多少？

如果可以将补贴限额设为无限大，请报告该限额。

【输入描述】

第一行输入 N N N和 M M M,接下来输入 N N N个数。

· 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2×10^5 1≤N≤2×105

· 1 ≤ M ≤ 2 × 1 0 （ 14 ） 1\leq M\leq 2×10^（14） 1≤M≤2×10（14）

· 1 ≤ A i ≤ 1 0 9 1\leq A_i\leq 10^9 1≤Ai​≤109

·所有输入值均为整数

【输出描述】

以整数的形式打印满足预算条件的补贴限额 x x x的最大值。

如果补贴限额可以无限大，则打印 “ i n f i n i t e ” “infinite” “infinite”

样例解释1

如果补贴限额设置为 2 2 2日元，则所有 N N N人的交通补贴额度为 m i n ( 2 , 1 ) + m i n ( 2 , 3 ) + m i n ( 2 , 2 ) + m i n ( 2 , 4 ) = 7 min(2,1) + min(2,3) + min(2,2) + min(2,4) = 7 min(2,1)+min(2,3)+min(2,2)+min(2,4)=7日元，在预算 8 8 8日元之内。

如果补贴限额设置为 3 3 3日元，则所有 N N N人的交通补贴额度为 m i n ( 3 , 1 ) + m i n ( 3 , 3 ) + m i n ( 3 , 2 ) + m i n ( 3 , 4 ) = 9 min(3,1) + min(3,3) + min(3,2) + min(3,4) = 9 min(3,1)+min(3,3)+min(3,2)+min(3,4)=9日元，超出预算 8 8 8日元。

因此，补贴额度的最大可能值为 2 2 2日元

样例解释2

交通费补助额的上限可以无限大

题目描述

あるイベントには $ N $ 人が参加し、$ i $ 番目の人の交通費は $ A_i $ 円でした。

イベントの主催者である高橋くんは、交通費補助額の上限額 $ x $ を設定して、人 $ i $ には交通費補助額として $ \min(x,A_i) $ 円を支給することとしました。ここで $ x $ は非負整数である必要があります。

高橋くんの予算が $ M $ 円であり、$ N $ 人に渡す交通費補助額の総和を $ M $ 円以下にしたいとき、交通費補助額の上限額 $ x $ は最大でいくらにできますか？

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりにそのことを報告してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_{N} $

输出格式

予算の条件を満たすときの交通費補助額の上限額 $ x $ の最大値を整数として出力せよ。

ただし、交通費補助額の上限額を無限に大きくできる場合は代わりに infinite と出力せよ。

样例 #1

样例输入 #1

4 8
1 3 2 4

样例输出 #1

2

样例 #2

样例输入 #2

3 20
5 3 2

样例输出 #2

infinite

样例 #3

样例输入 #3

10 23
2 5 6 5 2 1 7 9 7 2

样例输出 #3

2

提示

制約

• $ 1\leq\ N\leq\ 2\times\ 10^5 $
• $ 1\leq\ M\ \leq\ 2\times\ 10^{14} $
• $ 1\leq\ A_i\ \leq\ 10^9 $
• 入力される数値は全て整数

Sample Explanation 1

交通費補助額の上限額を $ 2 $ 円にすると、$ N $ 人に渡す交通費補助額の総和は $ \min(2,1)\ +\ \min(2,3)\ +\ \min(2,2)\ +\ \min(2,4)\ =\ 7 $ 円となり、予算の $ 8 $ 円以下となります。 交通費補助額の上限額を $ 3 $ 円にすると、$ N $ 人に渡す交通費補助額の総和は $ \min(3,1)\ +\ \min(3,3)\ +\ \min(3,2)\ +\ \min(3,4)\ =\ 9 $ 円となり、予算の $ 8 $ 円を超えてしまいます。 よって、交通費補助額の上限額の最大値は $ 2 $ 円となります。

Sample Explanation 2

交通費補助額の上限額を無限に大きくできます。

#include <iostream>

using namespace std;
long long int arr[1000005];
int n;
long long int m;
int check(long long int x) {
	long long int sum=0;
	for(int i=1; i<=n; i++) {
		sum +=min(x,arr[i]);
	}
	return sum<=m;
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>arr[i];
	}
	long long int left=1,right=m+1;
	long long int ans;
	while(left<=right) {
		long long mid=left+right>>1;
		if(check(mid)==1) {
			left=mid+1;
			ans=mid;
		} else {
			right=mid-1;
		}
	}
	if(ans==m+1) {
		cout<<"infinite";
	} else {
		cout<<ans;
	}
	return 0;
}