凉肝的比赛

0
16

对于这场比赛,我真的是有点划水了,做了俩题,做第三题的时候实在是不知道什么地方卡住了,然后我家来了客人,被带出去吃饭去了,ε=(´ο`*)))唉!!!

B – Just Eat It!

这道题是个经典的DP题,我对于递推还不是特别熟悉,得找到题目的状态转移方程。

B[ i ] =max{ A[ i ] ,B[ i – 1] + A[ i ] };

令B[i]表示以A[ i ]作为末尾的连续序列的最大和,通过设置一个B数组,数组最大连续子序列和其实就是B数组里的最大值,还有就是找到的最大值有可能也是所有的总和,所以先设置一个数,让它统计已经连续了多少,对于这种情况进行排除,然后对先前求出的总和进行比较,就能得到答案。

(这个方法我是从算法笔记上看到的,还有太多没看了…)

#include<bits/stdc++.h>
using namespace std;
const int xa=2e5+5;
long long a[xa],b[xa];
int main()
{
    int t;
    cin>>t;
    long long n;
    long long sum;
    long long shu;
    bool pan;
    while(t--){
        cin>>n;
        sum=0;
        shu=0;
        pan=false;
        for(int i=0;i<n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        b[0]=a[0];
        for(int i=1;i<n-1;i++){
            if(a[i]<=b[i-1]+a[i]){
                b[i]=b[i-1]+a[i];
                shu++;
            }else{
                b[i]=a[i];
                shu=0;
            }
        }
        if(shu==n){
            pan=true;
        }
        int k=0;
        for(int i=1;i<n;i++){
            if(b[i]>b[k]){
                k=i;
            }
        }
        if(b[k]>=sum&&!pan){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
}

E – Deadline

这题看起来挺简单的,但是这个数学问题的解法比赛的时候我是怎么都没想到,比赛的时候也是匆匆看了一眼就去看B题去了。

听大佬们说这个题是均值不等式

由题意得,n>=x+[d/(x+1)]=x+1[d/(x+1)]-1>=2sqrt(d)-1;

所以就解出来了 ~。~

呜呜呜~~

#include<bits/stdc++.h>
using namespace std;
int t;
long long n,d;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>d;
        if((n+1)*(n+1)/4>=d)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}    

<

发布回复

请输入评论!
请输入你的名字