被签到题wa跪orz

A-牛牛的三角形


题目

题目描述:
牛牛有一个数组长度大小为n,数组中有n个正整数。
现在牛牛请你从其中选出三个元素(注意选择元素的下标不能相同,但是其值可以相同)组成一个三角形。
无法做到,请输出一行一个字符串"No solution",反之请输出这三个元素的值。
如果有多种组成三角形的元素组合,你可以输出任意一种

输入描述:
第一行是一个正整数n,(3≤n≤102 )表示数组的元素个数。
接下来一行输入n个正整数(1≤ai≤109 )表示每个数组元素的值。

输出描述:
如无法做到,请输出一行一个字符串"No solution",反之请输出这三个元素的值。
如果有多种组成三角形的元素组合,你可以输出任意一种。


解析

这道题挺水的,就是从多个数里面选出三个数,进行操作就行了。

  • 数据很小,所以不会超时的。

打代码:
  1. 输入所有数据。
  2. 三重循环遍历:不要完完整整遍历了,考虑的重复可以不用遍历前面的。
  3. 见简单代码。


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),表示鱼缸的高度与长度,斜坡的高度与长度。

输出描述:
请输出一个实数,表示鱼缸最多能够放多少水,请输出水的体积。


解析

这道题直接是一道高中数学题,分类讨论就行了,我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)。

输出描述:
输出一个正整数表示问题的答案。


解析

这道题我咋看之下并没有什么思路。
但是换个角度思考,从答案的角度思考,我们的问题就变了(你问我为什么换角度?直觉(大佬的)):
  • 我们假设我们已经知道了接下来要过多少天。
  • 题目变成了:我们的水稻在全都长到最高之后,我们要经过多少次操作才能让他们全都变得相等(次数当然不能超过天数)。

这就是我们经典的二分法思想:
  • 既然如此,我们发现,我们题目的重要信息:操作的次数。呈线性(操作次数少了,表示当前天数不会更大,反之亦然)。

二分讲解:
  1. 那么操作次数少我们就选取小更小的天数,大就选更大的天数。这样我们的二分概念就出来了。
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    
    这就是二分的基本操作,这个我也就不细讲了。
  2. 二分结束之后呢,我们要讨论一下怎么去找操作的最小值了(也就是最少所要花的操作次数)。
  3. 这一步我们可以不用思考,因为我们知道,我们最后水稻的平衡高度肯定是其中一个水稻的高度
  4. 所以把在每个水稻上平衡的情况求出来就好了。这里为了节省时间开销,我们用了前缀和
    for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + b[i];
    
    这样可以方便我们求出操作次数(操作后总高度与操作前总高度的差值)。
  5. 然后因为我们的操作,有变短的也有边长的,所以要分类讨论,然后加起来:
    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后边变矮的操作了
  6. 那么最后,如果cnt的最小值比天数要小,表示:我们现在的这种方法可以,那么天数就可以试一试更小的可不可以,反之亦然。

我jio得讲的挺清楚了,打代码:
  1. 储存变量及数组。
  2. 二分查找答案,二分详情看上面的算法讲解。
  3. 看代码吧~


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;
}
//函数区