被签到题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; } //函数区