| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1723 人关注过本帖
标题:[没人气,抄道题] 分糖果
只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
结帖率:91.67%
收藏
已结贴  问题点数:100 回复次数:11 
[没人气,抄道题] 分糖果
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
    Each child must have at least one candy.
    Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
n个小孩站一排,每个小孩有一个等级值。现在分发糖果给他们,要求:
a. 每个小孩至少分到一颗糖。
b. 等级高的小孩要比靠近他的低等级小孩拿到的糖果多。
请计算最少需要多少糖果

例如6个小孩,等级分别是 1, 3, 7, 5, 3, 2
那么糖果得这样分才最少:1, 2, 4, 3, 2, 1
即对于 { 1, 3, 7, 5, 3, 2 } 这个数列,结果为 13
搜索更多相关主题的帖子: following children Children assigned minimum 
2015-08-06 12:59
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:15 
是不是这样理解呢:

比如:

小孩站队:  1  3  2  4  5  7  4  5  6  2
分果果    1  2  1  2  3  4  1  2  3  1

DO IT YOURSELF !
2015-08-06 13:36
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:0 
回复 2楼 wp231957
是的
2015-08-06 14:19
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
看起来很简单 其实不简单

[ 本帖最后由 wp231957 于 2015-8-6 14:26 编辑 ]

DO IT YOURSELF !
2015-08-06 14:25
kenierlee
Rank: 6Rank: 6
等 级:侠之大者
威 望:3
帖 子:58
专家分:474
注 册:2015-7-28
收藏
得分:0 
程序代码:
#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int f(int *ratings, int n)
{
    int count = 0, i, *candies = (int*)malloc(sizeof(int) * n);
    candies[0] = 1;
    for (i = 1; i < n; ++i)
    {
        candies[i] = 1;
        if (ratings[i] > ratings[i-1])
            candies[i] = candies[i-1] + 1;
    }
    count = candies[n-1];
    for (i = n - 2; i > -1; --i)
    {
        if (ratings[i] > ratings[i+1])
            candies[i] = MAX(candies[i], candies[i+1] + 1);
        count += candies[i];
    }
    free(candies);
    return count;
}

int main(void)
{
    int n, i, *ratings;
    scanf("%d", &n);
    ratings = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n; ++i)
        scanf("%d", ratings + i);
    printf("%d\n", f(ratings, n));
    free(ratings);
    return 0;
}
2015-08-06 14:39
lianyicq
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:26
帖 子:737
专家分:3488
注 册:2013-1-26
收藏
得分:15 
回复 楼主 rjsp
论坛最近总是很慢?
程序代码:
void main(void)
  {
     /*int r[10]={0,1,3,7,5,3,2,1,6,4};*/
     int r[7]={0,1,3,7,5,3,2};
     int c[7];
     int n,i,d,sum=0;
     system("cls");
     c[0]=0;
     d=c[0];
     for(n=1;n<7;n++)
       {
     if(r[n]>r[n-1])
       c[n]=++d;
     else if(r[n]==r[n-1])
       c[n]=d;
     else
       {
         c[n]=--d;
         if(c[n]==0)
          {
        for(i=n;i>0;i--)
          {
            c[i]++;
            if(c[i]>c[i-1]){d=1;break;}
          }
          }
       }
    }

  for(i=1;i<=6;i++)
    { printf("%d ",c[i]);
      sum=sum+c[i];
    }
  printf("\nsum=%d\n",sum);
  getch();
}

Tc2.0

[ 本帖最后由 lianyicq 于 2015-8-6 16:36 编辑 ]

大开眼界
2015-08-06 16:34
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:15 
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void divide(int *p,int n)
{
    int i;
    int *q = (int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
        q[i]=1;
    for(i=1;i<n;i++)
    {
        if(p[i]>p[i-1]&&q[i]<=q[i-1])
            q[i]=q[i-1]+1;
        else if(p[i]<p[i-1]&&q[i]>=q[i-1])
            q[i-1]=q[i]+1;
    }
    for(i=n-2;i>=0;i--)
    {
        if(p[i]>p[i+1]&&q[i]<=q[i+1])
            q[i]=q[i+1]+1;
    }
    for(i=0;i<n;i++)
        printf("%d ",q[i]);
    putchar(10);
    free(q);
}
int main()
{
  int n,i;
  scanf("%d",&n);
  int *p = (int*)malloc(n*sizeof(int));
  for(i =0;i<n;i++)
      scanf("%d",p+i);
  divide(p,n);
  free(p);
  return 0;
}

从左到右,从右到左各检查一遍

一片落叶掉进了回忆的流年。
2015-08-06 18:09
列车永不停息
Rank: 2
等 级:论坛游民
帖 子:76
专家分:48
注 册:2015-7-31
收藏
得分:15 
确实不简单,上面的程序我去测试了一下,好像都是错的。。。
2015-08-06 19:34
jklqwe111
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:35
帖 子:336
专家分:1135
注 册:2014-4-13
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n, i, *data;
    int fen(int*,int);
   
    scanf("%d", &n);
    data = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n; ++i) scanf("%d",&data[i]);
        
    printf("%d\n", fen(data, n));
    free(data);
    return 0;
}

int fen(int*data,int n)
{
  int i,sum=0,m,k,f;
  
  m=1;
  sum+=m;
  k=0;
  f=1;
  for(i=1;i<n;++i)
  {
  if (data[i]< data[i-1])
   {
        f=0;
      k++;
      m--;
      sum+=m;   
   }
  else
   {
        if(f==1)
          {
             m++;
           sum+=m;   
          }
      else
        {
             if(m<1)sum+=(k+1)*(1-m);
             if(m>1)sum-=k*(m-1);
             m=2;
             sum+=m;
             k=0;
             f=1;
        }
   }
  }
   if(f==0)
    {
     if(m<1)sum+=(k+1)*(1-m);
     if(m>1)sum-=k*(m-1);   
    }
return sum;   
}
从前向后一次遍历,以一升一降为一个周期,每个点,大于前驱加1,小于减1,用m记录,每一个周期末根据m的值调整数量。每一个周期所用数量,只与自身周期内的数据有关,与其前后数据无关,所以只要能处理一个周期,问题就可以解决,由于只要求数量,所以可以用一个变量记录所用数量,省去记录每个人的数量的数组,从而节省空间。
2015-08-06 20:44
calix
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:28
帖 子:249
专家分:1442
注 册:2015-5-4
收藏
得分:15 
应该是要考虑相等的情况的吧
程序代码:
#include <stdio.h>

#define N 10

compare(int *a, int *b, int i, int j){
    if(a[i] > a[j]){
        b[i] = b[j] + 1;
    }else if(a[i] < a[j]){
        if(b[j] - 1 <= 0){
            b[i] = 1;
            while(j >= 0 && a[j] >= a[j+1] && b[j] <= b[j + 1]){
                b[j--] += 1;
            }
        }else{
            b[i] = 1;
        }
    }else{
        b[i] = b[j];
    }
}

main()
{
    int a[N] = {1,6,2,3,7,7,4,5,6,2};
    int b[N] = {1};
    int i;
    for(i = 1; i < N; i++){
        compare(a, b, i, i - 1);
    }
    for(i = 0; i < N; i++){
        printf("%d ", a[i]);
    }
    putchar(10);
    for(i = 0; i < N; i++){
        printf("%d ", b[i]);
    }
}
2015-08-06 22:19
快速回复:[没人气,抄道题] 分糖果
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018031 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved