n个小孩站一排，每个小孩有一个等级值。现在分发糖果给他们，要求：
a. 每个小孩至少分到一颗糖。
b. 等级高的小孩要比靠近他的低等级小孩拿到的糖果多。
请计算最少需要多少糖果

例如6个小孩，等级分别是 1, 3, 7, 5, 3, 2
那么糖果得这样分才最少：1, 2, 4, 3, 2, 1
即对于 { 1, 3, 7, 5, 3, 2 } 这个数列，结果为 13

是不是这样理解呢：

比如：

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

是的

看起来很简单 其实不简单

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

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

论坛最近总是很慢?

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 编辑 ]

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

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

确实不简单，上面的程序我去测试了一下，好像都是错的。。。

#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的值调整数量。每一个周期所用数量，只与自身周期内的数据有关，与其前后数据无关，所以只要能处理一个周期，问题就可以解决，由于只要求数量，所以可以用一个变量记录所用数量，省去记录每个人的数量的数组，从而节省空间。

应该是要考虑相等的情况的吧

#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]);
    }
}