4125: 囧king玩插头
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 92  Solved: 12

Description
囧king是一个很犀利的人，没事就喜欢玩一玩插头（危险动作，请勿模仿）

囧king找到的是一个很长很长的插座，插座上一共有一排连续n个插孔，同时他还在旁边找到了一串插头，插头有两种类型。类型1要占1个插孔，类型2要占连续的两个插孔。囧king按顺序从前往后对这一串插头进行操作。他可以把插头插到插座上，插上时，会产生能量。不管是什么类型的插头，每当一个插头被插上时，都会产生1的能量。囧king也可以把之前插在插座上的插头拔掉人任意个，被拔掉的插头是不能再重新被插上的，当然囧king也能把当前的插头扔掉。每此操作后，他会计算一下，当前所有插头能产生的能量总和是多少，然后记在本子上，当所有的插头被用过了之后，他把所有的能量总和加起来，得到他最终获得的能量值。

但是危险的事情发生了，如果囧king把所有的插头都操作完之后，他得到的最终能量值并不是能获得的最大能量值，那么他将会被电击一下（危险动作，请勿模仿）。所以囧king很想知道他能获得的最终能量值的最大值会是多少。你能帮帮他吗？


Input
多组测试数据。每组数据第一行输入一个n(n<=10^5)，表示囧king找到的插头一共有n个插孔。第二行由一串1和2组成，表示囧king找到的一串插头，1表示1类型，2表示2类型。（囧king最多只能找到10^5个插头）


Output
输出一个值，表示囧king最终能获得的最大能量值。


Sample Input
4
211

Sample Output
6


我的代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 200000
int main()
{
    char c[MAXN],a[MAXN],b[MAXN],h[MAXN];
    int E,q,n,i,c1,c2,j,k,s;
    while(scanf("%d",&n)!=EOF)
    {
        getchar();
        gets(c);
        j=0;k=0;
        memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
        for(i=0;c[i]!='\0';i++)
        {
            if(c[i]=='1')
            {a[j]=c[i];
             j++;}
             else if(c[i]=='2')
             {b[k]=c[i];
              k++;}
          }
          c1=j;c2=k;
          memset(c,0,sizeof(c));
          strcpy(c,a);
          strcat(c,b);
          s=j+2*k;
          memset(h,0,sizeof(h));
          if(s<=n)
          {E=(1+c1+c2)*(c1+c2)/2;}
          else
          {i=0;j=0;
            while(j<=n-1)
            {
                if(c[i]=='1')
                {h[j]='1';i++;j++;c1--;}
                else
           {h[j]='2';h[j+1]='1';j=j+2;i++;c2--;}//设2类型插头占第一个插孔为'1',占第二个插孔为'2'
            }
            q=0;
            for(i=0;i<n;i++)
            {
                if(h[i]=='1'){q++;}
            }
            E=(1+q)*q/2;
            if(h[n-2]=='2'){E+=q*c2;}
            else
            {
                if(h[n-1]=='1'){E+=q*c1+(q-1)*c2;}
                else{E+=q*(c2+1);}
            }
        }
        if(E<0){E=0;}
        printf("%d\n",E);
    }
    return 0;
}
         
              
   
因为是新人，语言还不怎么熟。。
我的想法不知道行不行：
先把字符串中的1全部排前面，2全部排后面，组成新字符串，按顺序插到插孔中（也就是先插1插头再插2插头），如果全部插头插上去超过了插孔数的话，再判断n-1,n-2插孔的情况，计算总能量。。。

测试数据对了，但提交WRONG ANSWER,求解~~

还有，上面那个代码，在c-free上不能运行，显示ERROR: array size 200000 exceeded limit 20000 for evaluation edition
是char定义的字符串有最大上限的关系吗？这该怎么解决？

我是用动态内存运行的，测试了几个数据貌似都没错，虽然对指针还是一窍不通
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 200000
int main()
{
    char *c,*a,*b,*h;
    int E,q,n,i,c1,c2,j,k,s;
    c=malloc(sizeof(char)*200000);
    a=malloc(sizeof(char)*200000);
    b=malloc(sizeof(char)*200000);
    h=malloc(sizeof(char)*200000);
    if(c==NULL||a==NULL||b==NULL||h==NULL)
    exit(0);
    while(scanf("%d",&n)!=EOF)
    {
        getchar();
        gets(c);
        j=0;k=0;
        memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
        for(i=0;c[i]!='\0';i++)
        {
            if(c[i]=='1')
            {a[j]=c[i];
             j++;}
             else if(c[i]=='2')
             {b[k]=c[i];
              k++;}
          }
          c1=j;c2=k;
          memset(c,0,sizeof(c));//?
          strcpy(c,a);
          strcat(c,b);
          s=j+2*k;
          memset(h,0,sizeof(h));
          if(s<=n)
          {E=(1+c1+c2)*(c1+c2)/2;}
          else
          {i=0;j=0;
            while(j<=n-1)
            {
                if(c[i]=='1')
                {h[j]='1';i++;j++;c1--;}
                else
                {h[j]='2';h[j+1]='1';j=j+2;i++;c2--;}
            }
            q=0;
            for(i=0;i<n;i++)
            {
                if(h[i]=='1'){q++;}
            }
            E=(1+q)*q/2;
            if(h[n-2]=='2'){E+=q*c2;}
            else
            {
                if(h[n-1]=='1'){E+=q*c1+(q-1)*c2;}
                else{E+=q*(c2+1);}
            }
        }
        if(E<0){E=0;}
        printf("%d\n",E);
    }
    return 0;
}
         
              
   但这个代码交不上去，显示CE，函数返回值异常。。。哪位高人帮忙看下，或提供个更好的解答，跪谢！

求个思路。。。

if(c==NULL||a==NULL||b==NULL||h==NULL)
    exit(0); // 0表示正常结束, 但你这里应该是异常结束, 改成exit(1);试试, (猜的).
你的第二个程序可能内存使用多了点, 用一个char数组就可以了,

我的思路和你的差不多. 先排序, 求和方法是:
1. 先把插座插满, 插头插不满或刚好插满的话直接用s = 1+2+...+n = (n+1)n/2求结果.
2. 如果插座满了, 插头还有的话, 就先计算现在插头上p个的和,s = (p+1)p/2, 把剩余的一个一个插上去, 要考虑拨掉一个,还是拨掉两个的情况.
(如果原先是1, 又刚好插满, 再来一个2就要先拨掉两个), 计算和用 s = s + p或s = s + (p--);
我的代码是根据你的样例和第二个程序写的. 样例太少, 也不知道对不对. 不过有一点. 当n = 10万, 插头也是10万的时候, 结果是50亿, 我的电脑用什么数据类型都显示不了

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

#define SWAP(a, b, t) t = (a), (a) = (b), (b) = (t)

int main()
{
    int n, m;       // 插座孔的数量
    int i, j, t;
    int s, p;       // s 总和, p 插座上插头的数量
    char a[100001];

    while (scanf("%d", &n) == 1) {
        getchar();
        gets(a);

        p = s = 0;
        j = strlen(a);
        for (i = 0; i < j; i++)           // 排序
            if (a[i] == '2')        
                for (; j > i; j--)
                    if (a[j] == '1') {
                        SWAP(a[i], a[j], t);
                        break;
                    }
        j = strlen(a);
        if ((i + (j - i) * 2) <= n)      // 插座不满或刚好满直接求和.
            s = ((j + 1)*j)/2;
        else {
            i = 0;
            for (m = a[i] - '0'; m <=n; m += a[++i] - '0')    // 插座满时, 插头的个数
                p++;
            s = ((p + 1)*p)/2;                                // 计算刚插满时能量和.
            for (j = i-1; a[i]; i++, j++)                     // 一个一个插上剩余的插头
                if (a[i] != a[j] && m == n)   
                    s += --p;
                else
                    s += p;
        }
        printf("%d\n", s);
    }
    return 0;
}

.

如果你要用我的代码的话, 最好把 s 定义为long long类型, 我用int是因为我的电脑, 用int, long, unsigned long, long long, double 结果都是一个样,
你的电脑如果是64位, 而你的编译器又支持long long类型, 说不定可以输出50亿.