凉肝的比赛

2020-01-18 16:00:44来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

凉肝的比赛

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

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;
    }
}    


原文链接:https://www.cnblogs.com/yclW/p/12207720.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:寒假集训第一天---并查集题解

下一篇:BFS和队列