题解

48 条题解

  • 5
    @ 2017-03-15 13:22:18

    这是我的解题报告,大家看一下
    http://blog.csdn.net/qq_35904657/article/details/62220896

  • 3
    @ 2017-10-18 16:54:21

    这个题其实代码没任何难度,懂了原理肯定是会写的
    所以说这道题主要是想一下原理

    原题意是需要最后建成长度为n的一个建筑物,也就是这个建筑物宽度为n

    不妨将其视作要求建造一个长度为n+1的建筑物(0-n) 第0个位置高度为0

    那么则有:

    a[i]表示第i个位置的高度

    (1)若a[i]<=a[i-1]
    则a[i]是完全不需要考虑的,因为在能够搭建a[i-1]高度的同时向右延伸就顺便建造了
    (2)当a[i]>a[i-1]
    那么a[i]-a[i-1]的部分就需要在a[i]另外去建造,所以ans+=a[i]-a[i-1]

    结束

    #include<bits/stdc++.h>
    using namespace std;
    int a[100001];
    int main()
    {
        int n,ans=0; cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++)
        if(a[i]>a[i-1])
        ans+=(a[i]-a[i-1]);
        cout<<ans;
        return 0;
    }
    
  • 3
    @ 2016-11-15 14:27:09

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int M = 100005;

    int h[M];

    int main()
    {
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
    scanf("%d", &h[i]);
    if(h[i] < h[i-1]) ans += h[i-1] - h[i];
    }
    ans += h[n];
    printf("%d", ans);
    return 0;
    }

    • @ 2016-11-17 11:40:09

      你的算法太棒啦!!!!

    • @ 2017-07-26 17:16:16

      @BruseWayne: Batman is right.

  • 1
    @ 2018-12-13 21:38:10

    一个小优化,不开数组,空间复杂度O(1);
    #1 Accepted 1ms 324.0 KiB
    #2 Accepted 1ms 324.0 KiB
    #3 Accepted 1ms 316.0 KiB
    #4 Accepted 2ms 324.0 KiB
    #5 Accepted 1ms 316.0 KiB
    #6 Accepted 1ms 324.0 KiB
    #7 Accepted 1ms 316.0 KiB
    #8 Accepted 2ms 324.0 KiB
    #9 Accepted 5ms 316.0 KiB
    #10 Accepted 9ms 324.0 KiB

    #include<iostream>
    #include<algorithm>
    using namespace std;
    //呵呵
    //大神万岁
    
    //结构定义区
    
    //全局变量区
    int cur,last,n; 
    long long sum=0;
    //函数声明区
    
    //主函数开始!
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        last=0;
        for(int i=1;i<=n;i++)
        {
            cin>>cur;
            if(cur>last) sum+=(cur-last);
            last=cur;
        }
        cout<<sum<<endl;
    }
    //函数实现区
    
  • 0
    @ 2018-07-08 21:56:09

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll n,a[100001],b[100001],tree[400001],add[400001],uans,x,y,cnt;
    struct qu {
    ll a;
    ll b;
    };
    queue<qu> q;
    qu m,p;
    void build(ll pos,ll l,ll r) {
    add[pos]=0;
    if(l==r) {
    tree[pos]=a[l];
    return;
    }
    ll mid=(l+r)/2;
    build(pos*2,l,mid);
    build(pos*2+1,mid+1,r);
    tree[pos]=min(tree[pos*2],tree[pos*2+1]);

    }

    void convey(ll pos,ll l,ll r) {
    add[pos*2]+=add[pos];
    add[pos*2+1]+=add[pos];
    tree[pos*2]+=add[pos];
    tree[pos*2+1]+=add[pos];
    add[pos]=0;
    }

    void change(ll pos,ll l,ll r,ll sl,ll sr,ll c) {
    if(sl<=l&&r<=sr) {
    add[pos]+=c;
    tree[pos]+=c;
    return;
    }

    convey(pos,l,r);
    ll mid=(l+r)/2;
    if(sl<=mid) {
    change(pos*2,l,mid,sl,sr,c);
    }

    if(sr>=mid+1) {
    change(pos*2+1,mid+1,r,sl,sr,c);
    }

    }

    ll solve(ll pos,ll l,ll r,ll sl,ll sr) {
    if(sl<=l&&r<=sr) {
    return tree[pos];
    }

    convey(pos,l,r);
    ll ans=100000000000000;
    ll mid=(l+r)/2;
    if(sl<=mid) {
    ans=min(ans,solve(pos*2,l,mid,sl,sr));
    }

    if(sr>=mid+1) {
    ans=min(ans,solve(pos*2+1,mid+1,r,sl,sr));
    }

    return ans;
    }

    int main()
    {
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) {
    scanf("%lld",&a[i]);
    if(a[i]==0) {
    b[++cnt]=i;
    }

    }

    build(1,1,n);
    if(cnt>0) {
    for(ll i=1;i<=cnt;i++) {
    x=y+1;
    y=b[i];
    m.a=x;
    m.b=y-1;
    if(m.a<=m.b) {
    q.push(m);
    }

    }

    m.a=y+1;
    m.b=n;
    if(m.a<=m.b) {
    q.push(m);
    }

    }

    else {
    m.a=1;
    m.b=n;
    q.push(m);
    }

    while(!q.empty()) {
    p=q.front();
    q.pop();
    ll k=solve(1,1,n,p.a,p.b);
    uans+=k;
    change(1,1,n,p.a,p.b,-k);
    x=p.a-1;
    y=p.a-1;
    if(p.a==p.b) {
    continue;
    }

    for(ll i=p.a;i<=p.b;i++) {
    a[i]-=k;
    if(a[i]==0) {
    x=y+1;
    y=i;
    m.a=x;
    m.b=y-1;
    if(m.a<=m.b) {
    q.push(m);
    }

    }

    }

    m.a=y+1;
    m.b=p.b;
    if(m.a<=m.b) {
    q.push(m);
    }

    }

    printf("%lld",uans);
    return 0;
    }

    线段树模拟

  • 0
    @ 2017-11-11 20:56:58

    极限压行

    #include<stdio.h>
    int i,n,h[100001],ans=0;
    int main(){
        scanf("%d",&n);
        for(i=1;i<=n;i++) scanf("%d",&h[i]); h[n+1]=0;
        for(i=1;i<=n;i++) if(h[i]>h[i+1]) ans+=h[i]-h[i+1];
        printf("%d",ans); return 0;}
    
  • 0
    @ 2017-10-27 17:07:55

    水题
    边找拐点边模拟

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,x,k=0,s=0,m=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(x<k)
            {
                s+=k-m;
                m=x;
            }
            if(i!=n||x<k)
            k=x;
        }
        printf("%d",s+x-m);
        return 0;
    }
    

    空间复杂度O(1);

  • 0
    @ 2017-10-20 14:51:09

    分治rmq,每次找出最小值,计算并递归左右区间,记得用一个变量表示之前在这个区间已经搭建了多少
    /*program by mangoyang*/
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define LL long long
    #define INF (0x7f7f7f7f)
    #define Max(a,b) ((a) > (b) ? (a) : (b))
    #define Min(a,b) ((a) < (b) ? (a) : (b))
    #define N (100005)
    #define Pow (18)
    using namespace std;
    inline void read(int &x){
    int w = 1; char ch = 0; x = 0;
    while (ch ^ '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') w = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    x = x * w;
    }
    int f[N][Pow+1], g[N][Pow+1], a[N], n, ans;
    inline int Rmq(int l, int r){
    int d = (double) log2(r - l + 1);
    return f[l][d] < f[r-(1<<d)+1][d] ? g[l][d] : g[r-(1<<d)+1][d];
    }
    inline void solve(int l, int r, int used){
    if(l > r) return;
    int pos = Rmq(l, r);
    ans += a[pos] - used;
    solve(l, pos - 1, a[pos]);
    solve(pos + 1, r, a[pos]);
    }

    int main(){
    read(n);
    memset(f, 33, sizeof(f));
    for(int i = 1; i <= n; i++)
    read(a[i]), f[i][0] = a[i], g[i][0] = i;
    for(int j = 1; j <= Pow; j++)
    for(int i = 1; i <= n; i++){
    if(i + (1 << j - 1) > n) continue;
    if(f[i][j-1] < f[i+(1<<j-1)][j-1])
    f[i][j] = f[i][j-1], g[i][j] = g[i][j-1];
    else f[i][j] = f[i+(1<<j-1)][j-1], g[i][j] = g[i+(1<<j-1)][j-1];
    }
    solve(1, n, 0);
    printf("%d\n", ans);
    return 0;
    }

  • 0
    @ 2017-10-05 16:53:26

    //10行
    #include<iostream>
    using namespace std;
    int n,ans,i,a[100010];
    int main()
    { cin>>n;
    for(i=1;i<=n;i++)
    {cin>>a[i];
    if(a[i]-a[i-1]>0)ans+=(a[i]-a[i-1]);}
    cout<<ans;
    return 0;}

  • 0
    @ 2017-09-11 08:49:02

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,x,p,ans;
    int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    scanf("%d",&x);
    int k=x-p;
    if(k>0)ans+=k;
    p=x;
    }
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2016-10-30 10:46:05
    #include<iostream>
    using namespace std;
    int h[100001];
    int main()
    {
        int n,mmin=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>h[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(h[i]>h[i-1])
            {
                mmin+=(h[i]-h[i-1]);
            }
        }
        cout<<mmin;
        return 0;
    }
    
  • 0
    @ 2016-10-09 21:58:23

    1.第一块积木永远是要堆好,才去考虑下一块积木
    2.假设第二块积木比第一块高,那么就需要补齐
    3.假设第二块积木比第一块低,那么堆第一块积木的时候已经堆好第二块积木
    以此类推

  • 0
    @ 2013-11-23 19:53:10

    o(n)秒过啊啊啊啊啊啊

    5555555

  • 0
    @ 2013-11-23 19:51:35

    #include<iostream>
    using namespace std;
    int s={0},n,a[1000001]={0};
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    if(a[i]>a[i-1]) s=s+a[i]-a[i-1];
    }

    cout<<s;
    return 0;
    }
    水………………
    可是 考试时
    竟然爆0了 超空间了

  • 0
    @ 2013-11-22 01:14:19

    9行......
    program p1844;
    var a:array[0..100002] of longint;
    n,i,sum:longint;
    begin
    read(n);
    for i:=1 to n do read(a[i]);
    for i:=0 to n do sum:=sum+abs(a[i+1]-a[i]);
    write(sum div 2);
    end.

    • @ 2014-11-06 13:12:01

      你是怎么想的,能把思路说一说吗

  • 0
    @ 2013-11-19 21:11:30

    var
    i,j,n,m:longint;
    ans:int64;
    a:array[-1..100000] of longint;
    begin
    readln(n);
    ans:=0;
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n do
    if a[i]>a[i-1] then ans:=ans+a[i]-a[i-1];
    writeln(ans);
    end.

  • 0
    @ 2013-11-18 18:20:12

    说说咱的做法...
    o(nlogn)的算法,没想到o(n)的....
    首先可以知道对于区间【s,t】最少的步骤明显就是每一次都选择最低的那块积木,然后整个区间累加到那块积木的高度,然后再递归【s,k-1】和【k+1,t】,所以为了最快的找出区间最小值,要写RMQ的ST算法。
    然后就只要递归模拟就可以了。但是由于数据范围超100000,直接递归强一点的数据会爆栈...所以得手写一个人工栈。
    模拟的复杂度O(N),ST预处理O(NlogN)...然后就可以了...

  • 0
    @ 2013-11-16 16:53:18

    var
    n,i,j,total:longint;
    h:array [1..100000] of longint;

    begin
    read(n);
    for i:=1 to n do read(h[i]);
    total:=h[1];
    for j:=2 to i do
    begin
    if h[j-1]<h[j] then inc(total,(h[j]-h[j-1]));
    end;
    writeln(total);
    end.

  • 0
    @ 2013-11-15 23:30:23

    var
    i,j,n,m:longint;
    ans:int64;
    a:array[-1..100000] of longint;
    begin
    readln(n);
    ans:=0;
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n do
    if a[i]>a[i-1] then ans:=ans+a[i]-a[i-1];
    writeln(ans);
    end.

信息

ID
1844
难度
4
分类
(无)
标签
递交数
3960
已通过
1682
通过率
42%
上传者