【牛客练习赛63】
被签到题wa跪orz
题目描述：
如果有多种组成三角形的元素组合，你可以输出任意一种
输入描述：
第一行是一个正整数n，(3≤n≤102 )表示数组的元素个数。
接下来一行输入n个正整数(1≤ai≤109 )表示每个数组元素的值。
输出描述：
如无法做到，请输出一行一个字符串"No solution"，反之请输出这三个元素的值。
如果有多种组成三角形的元素组合，你可以输出任意一种。
忽略斜坡与鱼缸因为重心的影响而导致整个鱼缸打翻的情况，你可以认为鱼缸是粘在斜坡上面的，而斜坡粘在地面上无法移动。
题目描述：
牛牛看到菜园中的水稻参差不齐十分难受，请问至少在第几天，他能够让所有的水稻都长到同一个高度？
输入描述：
第一行是一个正整数n( 1 ≤ n ≤ 105 )，表示有菜园有n块菜地。
接下来一行输入n个正整数，表示每块菜地上水稻的高度，水稻的高度1 ≤ a[i] ≤ 109。
输出描述：
输出一个正整数表示问题的答案。
A-牛牛的三角形
题目
题目描述： 牛牛有一个数组长度大小为n，数组中有n个正整数。
现在牛牛请你从其中选出三个元素（注意选择元素的下标不能相同，但是其值可以相同）组成一个三角形。
无法做到，请输出一行一个字符串"No solution"，反之请输出这三个元素的值。如果有多种组成三角形的元素组合，你可以输出任意一种
输入描述：
第一行是一个正整数n，(3≤n≤102 )表示数组的元素个数。
接下来一行输入n个正整数(1≤ai≤109 )表示每个数组元素的值。
输出描述：
如无法做到，请输出一行一个字符串"No solution"，反之请输出这三个元素的值。
如果有多种组成三角形的元素组合，你可以输出任意一种。
解析
这道题挺水的，就是从多个数里面选出三个数，进行操作就行了。
- 数据很小，所以不会超时的。
打代码：
- 输入所有数据。
- 三重循环遍历：不要完完整整遍历了，考虑的重复可以不用遍历前面的。
- 见简单代码。
AC代码
#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
const int MAX = 1e2 + 7;
int a[MAX];
//全局变量区
int main() {
IOS;
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (a[i] + a[j] > a[k] && a[i] + a[k] > a[j] && a[j] + a[k] > a[i]) {
printf("%d %d %d\n", a[i], a[j], a[k]);
return 0;
}
printf("No solution\n");
return 0;
}
//函数区
B-牛牛的鱼缸
题目
题目描述：
牛牛有一个长为l,宽为1,高为h的鱼缸，现在他想要在鱼缸中盛一些水。他想要知道这个鱼缸最多能够放多少水。
当然这个问题太过于简单，所以牛牛将这个鱼缸放到了一个长为L,高为H的斜坡上面，如图所示，鱼缸宽度为1的这条边紧紧靠在斜坡与地面的交界线上。 
忽略斜坡与鱼缸因为重心的影响而导致整个鱼缸打翻的情况，你可以认为鱼缸是粘在斜坡上面的，而斜坡粘在地面上无法移动。
输入描述：
仅一行，输入四个整数h,l,H,L,(1≤h,l,H,L≤1041 \leq h,l,H,L \leq 10^41≤h,l,H,L≤104)，表示鱼缸的高度与长度，斜坡的高度与长度。
仅一行，输入四个整数h,l,H,L,(1≤h,l,H,L≤1041 \leq h,l,H,L \leq 10^41≤h,l,H,L≤104)，表示鱼缸的高度与长度，斜坡的高度与长度。
输出描述：
请输出一个实数，表示鱼缸最多能够放多少水，请输出水的体积。
请输出一个实数，表示鱼缸最多能够放多少水，请输出水的体积。
解析
这道题直接是一道高中数学题，分类讨论就行了，我wawawawawawawawawa了九遍。
我wa哭了。。。就是把字母打错了，我太难了orz
话不多说直接上图：
然后相似三角形，就能求出前一个是：
h * h * L / (2 * H)
后一个是：
(2 * h * L * l - H * l * l) / (2 * L)
打代码：
- 输入输出，哈哈哈哈
AC代码
#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
int main() {
IOS;
double h, l, H, L; cin >> h >> l >> H >> L;
if (h * L <= H * l) printf("%.8f\n", h * h * L / (2 * H));
else printf("%.8f\n", (2 * h * L * l - H * l * l) / (2 * L));
return 0;
}
//函数区 C-牛牛的揠苗助长
题目
题目描述： 牛牛有一块长度大小为n的菜园，他首先对这块菜园从1到n进行了编号，每一块地分别为1号、2号...n号菜地。
然后他往每块菜地中都种下了一些水稻，一开始，第i块菜地中的水稻高度均为a[i]个单位。
然后我们知道水稻的生长周期都是n天，也就是说每逢n天水稻就会长高一个单位，但是不巧的是整个菜园中每一块菜地的生长周期都错开了。
具体来说，第1天的时候第1块菜地中的水稻长高一个单位，第2天的时候第2块菜地中的水稻长高一个单位....第n天的时候第n块菜地中的水稻长高一个单位，接下来第n+1天，又轮到第1块菜地中的水稻长高一个单位以此类推。
每天在水稻进行自然生长之后，牛牛可以施展他神奇的魔法，这个魔法可以让任意一块菜地中的水稻长高一个单位，或者让任意一块菜地中的水稻缩短一个单位，当然啦，他也可以不进行任何操作。牛牛看到菜园中的水稻参差不齐十分难受，请问至少在第几天，他能够让所有的水稻都长到同一个高度？
输入描述：
第一行是一个正整数n( 1 ≤ n ≤ 105 )，表示有菜园有n块菜地。
接下来一行输入n个正整数，表示每块菜地上水稻的高度，水稻的高度1 ≤ a[i] ≤ 109。
保证一开始输入时水稻的高度不全都相同（数据保证答案至少为1）。
输出一个正整数表示问题的答案。
解析
这道题我咋看之下并没有什么思路。
但是换个角度思考，从答案的角度思考，我们的问题就变了（你问我为什么换角度？直觉（大佬的））：
- 我们假设我们已经知道了接下来要过多少天。
- 题目变成了：我们的水稻在全都长到最高之后，我们要经过多少次操作才能让他们全都变得相等（次数当然不能超过天数）。
这就是我们经典的二分法思想：
- 既然如此，我们发现，我们题目的重要信息：操作的次数。呈线性（操作次数少了，表示当前天数不会更大，反之亦然）。
二分讲解：
- 那么操作次数少我们就选取小更小的天数，大就选更大的天数。这样我们的二分概念就出来了。
while (l <= r) { ll mid = l + r >> 1; if (check(mid)) { r = mid - 1; ans = mid; } else l = mid + 1; }这就是二分的基本操作，这个我也就不细讲了。 - 二分结束之后呢，我们要讨论一下怎么去找操作的最小值了（也就是最少所要花的操作次数）。
- 这一步我们可以不用思考，因为我们知道，我们最后水稻的平衡高度肯定是其中一个水稻的高度。
- 所以把在每个水稻上平衡的情况求出来就好了。这里为了节省时间开销，我们用了前缀和。
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + b[i];这样可以方便我们求出操作次数（操作后总高度与操作前总高度的差值）。 - 然后因为我们的操作，有变短的也有边长的，所以要分类讨论，然后加起来：
cnt = i * b[i] - sum[i] + sum[n] - sum[i] - (n - i) * b[i]; //前面的i * b[i] - sum[i]就是在i前面进行长高的操作，sum[n] - sum[i] - (n - i) * b[i]就是i后边变矮的操作了
- 那么最后，如果cnt的最小值比天数要小，表示：我们现在的这种方法可以，那么天数就可以试一试更小的可不可以，反之亦然。
我jio得讲的挺清楚了，打代码：
- 储存变量及数组。
- 二分查找答案，二分详情看上面的算法讲解。
- 看代码吧~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 1e5 + 7;
ll n, a[MAX], b[MAX];
//全局变量区
int check(ll p);
//函数预定义区
int main() {
IOS;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
ll l = 1, r = 1e18, ans = 0;
while (l <= r) {
ll mid = l + r >> 1;
if (check(mid)) {
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
//二分找答案
cout << ans << endl;
}
int check(ll x) {
for (int i = 1; i <= n; i++) {
b[i] = a[i] + x / n;
if (x % n >= i) b[i]++;
}
sort(b + 1, b + 1 + n);
ll sum[MAX]; sum[0] = 0;
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + b[i];
ll mn = INF;
for (int i = 1; i <= n; i++)
mn = min(mn, i * b[i] - sum[i] + sum[n] - sum[i] - (n - i) * b[i]);
return mn <= x;
}
//函数区比赛 文章被收录于专栏
憨憨的专栏
携程公司氛围 79人发布
投递快手等公司10个岗位