牛客练习赛63

A.牛牛的三角形

输出边长能组成三角形的三条边或者"No solution"

Solution

暴力瞎搞搞

其实排序之后可以优化到但是不影响能过。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 100 + 5;

int n;
ll a[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;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]) {cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<'\n';return 0;}
    cout<<"No solution\n";
    return 0;
}

B.牛牛的鱼缸

Solution

分类讨论，简单计算几何。
两种情况:

1. 此时为一个未超过鱼缸对角线的三角形
2. 此时矩形减去上面的三角形即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    double h,l,H,L;cin>>h>>l>>H>>L;
    if(h*L<=l*H) cout<<fixed<<setprecision(8)<<0.5*h*h*L/H<<'\n';
    else cout<<fixed<<setprecision(8)<<h*l-l*l*H*0.5/L<<'\n';
    return 0;
}

C.牛牛的揠苗助长

Solution

前置知识：最优策略一定是将所有水稻都向某一个水稻看齐，也就是至少有一颗水稻是不用动的。(比赛的时候感觉是这样的
答案显然具有单调性，二分答案即可。问题转换为怎么写check函数。
很容易知道对于可以对取模，因为所有都加1和不加一样不影响结果。对取模后的新数组排序，求前缀和和后缀和(不求也没关系，只要能表示前后的贡献就好了，这里为了给大家看起来清楚一点)，遍历，记录最小改变次数即可。对于改变到所在的所需要的改变次数为。若最少需要的改变次数，返回true，反之false。

比赛的时候脑残的一笔没排序。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int n;
ll a[N],b[N];
ll pre[N],suf[N];

bool check(ll x){
    ll t=x%n;
    for(int i=1;i<=n;i++){
        if(i<=t) b[i]=a[i]+1;
        else b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) pre[i]=b[i]+pre[i-1];
    for(int i=n;i>=1;i--) suf[i]=b[i]+suf[i+1];
    ll ans=1ll<<62,tot=0;
    for(int i=1;i<=n;i++){
        tot=b[i]*(i-1)-pre[i-1]+suf[i+1]-b[i]*(n-i);
        ans=min(tot,ans);
    }
    return x>=ans?true:false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll L=1,R=1ll<<62,mid,ans=1;
    while(L<R){
        mid=(L+R)/2;
        if(check(mid)) R=mid,ans=mid;
        else L=mid+1;
    }
    cout<<ans<<'\n';
    return 0;
}