首页 > 技术文章 > HDU6486-Flower

FrankOu 2021-04-15 23:24 原文

题目传送门

题目分析:

题意:给你\(n\)束花,每次你能减去\(n-1\)束花\(1cm\)的高度,问你最后能否让所有花一样高

每次让\(n-1\)束花的高度减1,换个角度看就是让某一束花的高度加1,所以这道题就变成了让所有花长到同一高度。为了尽可能的避免让花剪光,转化成增加高度方面,就成了让花朵增加的高度尽可能的少,所以这个问题就成了让所有花朵从\(h_i\)长成最高的花朵\((maxH)\)需要多少次。

所以答案\(\text{ans=}\sum_{i=1}^n (maxH-h_i)\)

但是当\(ans\ge maxH\)时,答案不存在,因为取极限情况\(\lbrace 1,maxH\dots,maxH\rbrace\)下,需要经过\(maxH-1\)次才能让花都剪到同一高度,超过这个次数后花就都剪秃了。

AC代码

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rT printf("\nTime used = %.3lf\n", (double)clock()/CLOCKS_PER_SEC)
using namespace std;
int t, n;
int main() {
	io;
	cin >> t;
	while (t --) {
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		int maxh = *max_element(a.begin(), a.end()); // 找最大高度
		int sum = 0;
		for(auto v : a) sum += maxh - v;
		if(sum < a[n - 1]) cout << sum << '\n';
		else cout << -1 << '\n';
	}
	
	return 0;
}

推荐阅读