CCF 入门(我咋那么菜)小熊的果篮
小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子,从左到右依次用正整数 1 2 3 n 编号。连续排在一起的同一种水果称为一个“块”。
小熊要把这一排水果挑到若干个果篮里,具体方法是:每次都把每一个“块”中最左边的水果同时挑出,组成一个果篮。重复这一操作,直至水果用完。注意,每次挑完一个果篮后,“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后,两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。
#include<iostream>
#include<cstring>
#include<string>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<deque>
using namespace std;
int n,a[10001],l[10001],r[10001];
deque<int> b;
int main()
{
scanf("%d",&n);
a[0]=a[n+1]=-1;
r[0]=1;
l[n+1]=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=a[i-1])
{
b.push_back(i);
}
l[i]=i-1,r[i]=i+1;
}
while(r[0]!=n+1)
{
deque<int> t;
for(int i=0;i<b.size();i++)
{
printf("%d ",b[i]);
int u=l[b[i]],v=r[b[i]];
r[u]=v;
l[v]=u;
if(a[b[i]]!=a[u]&&a[b[i]]==a[v])
{
t.push_back(v);
}
}
printf("\n");
b=t;
}
return 0;
}
40分 运行错误
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct block
{
int value;
int count;
int begin;
};
int main()
{
int n = 0;
scanf("%d", &n);
vector<block> myblocks;
int intput = 0;
for (int i=1; i<=n; i++)
{
scanf("%d", &intput);
if (0 == myblocks.size())
{
block first_block;
first_block.value = intput;
first_block.count = 1;
first_block.begin = i;
myblocks.push_back(first_block);
}
else
{
block &cur_block = myblocks.back();
if (intput == cur_block.value)
{
cur_block.count++;
}
else
{
block new_block;
new_block.value = intput;
new_block.begin = i;
new_block.count = 1;
myblocks.push_back(new_block);
}
}
}
while (0 != myblocks.size())
{
vector<block>::iterator iter = myblocks.begin();
int cur_value = -1;
while (iter != myblocks.end())
{
if (0==(*iter).count)
{
iter = myblocks.erase(iter);
continue;
}
else
{
if (cur_value != (*iter).value)
{
cout << (*iter).begin << ' ';
cur_value = (*iter).value;
(*iter).begin++;
(*iter).count--;
}
iter++;
}
}
cout << endl;
}
return 0;
}