/ Vijos / 题库 / 积木大赛 /

题解

49 条题解

  • 0
    @ 2013-11-12 20:31:42

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int h[100000],a[100000];
    bool f(int c[],int d[],int n)
    {
    int sign = 0,i = 1;
    while (i <= n)
    {
    if (c[i] < d[i]) sign = 1;
    i++;
    }
    if (sign == 1) return false;
    else return true;
    }
    int main()
    {
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    int n , i ,j , l , r , sign;
    scanf("%d",&n);
    i = 1;
    while (i <= n)
    {
    scanf("%d",&h[i]);
    i++;
    }
    i = 1;
    for (sign = 0 ; i <= n ; i++)
    {
    if (a[i]<h[i])
    {
    l = i;
    for (j = i+1;j <= n+1;j++)
    {
    if (a[j]==h[j])
    {
    r = j - 1;
    break;
    }
    }
    for (j = l;j <= r ; j++)
    {
    a[j]++;
    }
    sign++;
    if (f(a,h,n)==true) break;
    else i = 0;
    }
    }
    printf("%d",sign);
    fclose(stdin);
    fclose(stdout);
    return 0;
    }

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

    ###O(n)算法一:
    #include <cstdio>
    #define MAXN 100010
    int h[MAXN],ans=0,n;
    int main() {
    h[0]=0;
    scanf("%d",&n);
    for (int i=0;i++<n;) {
    scanf("%d",&h[i]);
    if (h[i]>h[i-1]) ans+=h[i]-h[i-1];
    }
    printf("%d\n",ans);
    return 0;
    }
    ###O(n)算法二:
    #include <iostream>
    #include <cstring>

    using namespace std;

    #define MAXH 10010
    #define MAXN 100010

    struct node {
    node *next;
    int t;
    node () {
    next=NULL;
    }
    } *head[MAXH];

    int maxh=0;

    void Insert(int h,int t) {
    maxh=max(maxh,h);
    node *p=new(node);
    p->t=t,p->next=head[h];
    head[h]=p;
    }

    int n,h,delta=1,ans=0;
    bool f[MAXN];

    int main() {
    memset(f,true,sizeof(f)),memset(head,0,sizeof(head));
    cin>>n;
    f[0]=f[n+1]=false;
    for (int i=0;i++<n;) cin>>h,Insert(h,i);
    for (int i=0;i<=maxh;i++) {
    if (i) ans+=delta;
    for (node *p=head[i];p;p=p->next) {
    if (f[p->t-1]&&f[p->t+1]) delta++;
    if ((!f[p->t-1])&&(!f[p->t+1])) delta--;
    f[p->t]=false;
    }
    }
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2013-11-12 18:08:14

    O(nlogn)的算法 C++

    #include <iostream>
    using namespace std;

    int a[100008];
    int c=0;

    void work(int l,int r,int offset){
    int min=1000000;
    int i,ptr;
    if (l>r) return;
    for(i=l;i<=r;i++){
    if(a[i]<min) {min=a[i];ptr=i;};
    };
    c+=min-offset;
    work(l,ptr-1,min);
    work(ptr+1,r,min);
    return;
    }

    int main(){
    int n,i;
    cin>>n;

    for(i=0;i<n;i++){
    cin>>a[i];
    };

    work(0,n,0);
    cout<<c;

    return 0;
    }

  • -1
    @ 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;
    }

    线段树模拟

  • -1
    @ 2017-10-26 18:02:12

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int a[1001000];
    int b[1001000];
    int main()
    {
    int n,t=0,pd=0,first=0;
    cin>>n;
    cin>>a[1];
    for (int i=2;i<=n;++i)
    {
    cin>>a[i];
    if (a[i]<a[i-1] && first==0)
    {
    first=1;
    pd=1;
    t=t+1;
    b[t]=a[i-1]-b[t];
    }
    else if(pd==1 && a[i]>a[i-1])
    {
    first=0;
    pd=0;
    b[t+1]=a[i-1];
    }
    }
    if (pd==0) b[t+1]=a[n]-b[t+1];
    int end=0;
    for (int i=1;i<=t+1;++i) end=end+b[i];
    cout<<end<<endl;
    }

  • -1
    @ 2017-10-26 18:01:55

    我也来提供一种方法~
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int a[1001000];
    int b[1001000];
    int main()
    {
    int n,t=0,pd=0,first=0;
    cin>>n;
    cin>>a[1];
    for (int i=2;i<=n;++i)
    {
    cin>>a[i];
    if (a[i]<a[i-1] && first==0)
    {
    first=1;
    pd=1;
    t=t+1;
    b[t]=a[i-1]-b[t];
    }
    else if(pd==1 && a[i]>a[i-1])
    {
    first=0;
    pd=0;
    b[t+1]=a[i-1];
    }
    }
    if (pd==0) b[t+1]=a[n]-b[t+1];
    int end=0;
    for (int i=1;i<=t+1;++i) end=end+b[i];
    cout<<end<<endl;
    }

  • -1
    @ 2016-11-18 21:14:48 
    program
    block;

var
    n: longint;
    h: array [1..100000] of integer;
    i, ans: longint;

begin
//    assign(input, 'block.in'); assign(output, 'block.out');
//    reset(input); rewrite(output);
    read(n, h[1]);
    for i := 2 to n do
    begin
        read(h[i]);
        if h[i] > h[i-1] then
            inc(ans, h[i] - h[i-1]);
    end;
    inc(ans, h[1]);
    write(ans);
//    close(input); close(output);
end.
  • -1
    @ 2016-10-29 11:16:30

    想不到我的** AC100 竟会是这样的水题**。
    纯贪心，只要没有堆满就继续堆，直到遇到堆满为止。

    program buildings;
var n,i,ans,l:longint;
h,a:array[1..100000]of longint;

begin
  readln(n);
  for i:=1 to n do read(h[i]);

  fillchar(a,sizeof(a),0);
  ans:=0;
  l:=1;                             //l表示从第l个位置开始

  while l<=n do
  begin
    if a[l]=h[l] then
    begin
      inc(l);
      continue;
    end;

    for i:=l to n do
    begin
      if a[i]=h[i] then break;
      inc(a[i]);
    end;

    inc(ans);
  end;

  writeln(ans);
end.
  • -1
    @ 2016-09-25 20:13:04

    水。。都能用JAVA了
    java
    import java.util.*;
    public class Main {
    public static void main(String[] args) {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt(),last=0,ans=0;
    while(n!=0){
    int x=in.nextInt();
    if(x>last){
    ans=ans+(x-last);
    }
    last=x;
    --n;
    }
    System.out.println(ans);
    }
    }

  • -1
    @ 2016-09-20 12:20:01

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[100010];
    int f[100010];
    int main()
    {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    }
    f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
    if(a[i]>a[i-1])
    {
    f[i]=f[i-1]+a[i]-a[i-1];
    }
    if(a[i]<=a[i-1])
    {
    f[i]=f[i-1];
    }
    }
    printf("%d",f[n]);
    }

  • -1
    @ 2016-09-07 23:04:07

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[100010],s=0;
    int main()
    {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    if(a[i]>a[i-1])
    {
    s+=a[i]-a[i-1];
    }
    }
    cout<<s;
    return 0;
    }
    O(n)

  • -1
    @ 2016-08-28 15:19:42

    已经想不出更好更简洁的算法了。也找不到更水的题目了……
    c++
    #include <cstdio>
    int main()
    {
    int n,last=0,ans=0,h;
    scanf("%d",&n);
    while(n--)
    {
    scanf("%d",&h);
    ans+=h-last>0?h-last:0;
    last=h;
    }
    printf("%d",ans);
    return 0;
    }

  • -1
    @ 2016-07-27 08:26:48 
    #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>

using namespace std;

int main()
{ 
    int n;
    cin>>n;
    int ans=0,last=0,x;
    for(int i=1;i<=n;i++)
    {
       cin>>x;
       ans+=max(x-last,0);
       last=x;
    }
    cout<<ans;
    return 0;
}
  • -1
    @ 2016-05-20 17:11:06 
    #include<iostream>
using namespace std;
int n,l=0,r,num=0;
int main()
{
    cin>>n;
    for(int a=1;a<=n;a++)
    {
        cin>>r;
        if(r>l) num+=r-l;
        l=r;
    }
    cout<<num;
}
  • -1
    @ 2016-02-09 18:08:23

    天啊为什么只有我想到这种坑爹做法...
    先按高度递增排序，然后从下往上扫（只需维护当前有多少个断开的区间，分两类情况做加减法就可以了。代码中的变量area就是用来干这个的）。以下代码中排序省略...

    #include <stdio.h>
    #include <string.h>

    typedef struct {
    int height, index;
    } Block;
    Block arr[100005];
    int used[100005];

    int main(){
    int num, i, area, result;

    scanf("%d", &num);
    memset(used, 0, sizeof used);
    for(i=1; i<=num; i++){
    arr[i].index = i;
    scanf("%d", &arr[i].height);
    }
    quickSort(1, num);

    area = 1;
    result = 0;
    arr[0].height = 0;
    used[0] = used[num+1] = 1; //boundary
    for(i=1; i<=num; i++){
    used[arr[i].index] = 1;
    result += (arr[i].height - arr[i-1].height)*area;
    if(used[arr[i].index-1] + used[arr[i].index+1] == 0)
    area++;
    else if(used[arr[i].index-1] + used[arr[i].index+1] == 2)
    area--;
    }
    printf("%d\n", result);

    return 0;
    }

  • -1
    @ 2016-01-28 20:29:44 
    #include<iostream>
using namespace std;
int main(){
    int n, count = 0, thiss = 0, first = 0, last = 0, plus = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> thiss;
        if(thiss < last) count -= thiss, first = thiss, count += thiss, plus = thiss;
        else if(thiss > plus) count -= plus, count += thiss, plus = thiss;
        last = thiss;
    }
    cout << count;
    return 0;
}
  • -1
    @ 2015-10-24 11:10:02

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n , minn , x , ans;
    int main(){
    freopen( "block.in" , "r" , stdin );
    freopen( "block.out" , "w" , stdout );
    scanf( "%d%d" , &n , &x );
    minn = x;
    ans = x;
    for( int i = 2 ; i <= n ; i++ ){
    scanf( "%d" , &x );
    if ( minn >= x ) minn = x;
    else{
    ans += ( x - minn );
    minn = x;
    }
    }
    printf( "%d" , ans );
    fclose( stdin );
    fclose( stdout );
    return 0;
    }

  • -1
    @ 2015-10-12 09:45:55

    O(N)贪心
    var
    ans,x,n,i,h:longint;
    begin
    readln(n);
    read(x);
    ans:=x; h:=x;
    for i:=2 to n do
    begin
    read(x);
    if h>=x then
    begin
    h:=x;
    end else
    begin
    ans:=ans+(x-h);
    h:=x;
    end;
    end;
    writeln(ans);
    end.

  • -1
    @ 2015-09-27 19:56:56

    还要多水！！！
    #include<cstdio>
    using namespace std;
    long n,h[100001]={0},i,ans=0;
    int main(){
    scanf("%ld",&n);
    for(i=1;i<=n;++i)scanf("%ld",&h[i]);
    for(i=1;i<=n;++i)
    if(h[i]>h[i-1])ans+=h[i]-h[i-1];
    printf("%ld",ans);
    }

  • -1
    @ 2015-07-16 16:53:49

    #include<iostream>
    int a[100010],n,ans;
    int main()
    {
    std::cin>>n;
    for(int i=1;i<=n;i++) std::cin>>a[i];
    for(int i=1;i<=n;i++) ans+=std::max(0,a[i]-a[i+1]);
    std::cout<<ans;
    }
    9行的代码AC掉，就是任性23333

积木大赛

信息

ID
1844
难度
4
分类
(无)
标签
递交数
4002
已通过
1714
通过率
43%
被复制
9
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1