3-4 数据结构--横截面图上的面积
3-4 数据结构--横截面图上的面积
·
你的任务是模拟洪水灾害。
对于给定的横截面图,给出淹没部分的面积。
假设该地区不断地下雨,而从该地区溢出的水正在落入两侧的海中。 例如,对于上面的横截面图,雨水将产生洪水,其面积分别为 4、2、1、19 和 9。
输入
在一行中给出一个字符串,分别用"/",""和"_"表示斜坡和平原。 例如,上面例子的区域由字符串“\ \ / / / \ _ / \ / \ \ \ \ / _ / \ \ / / / _ _ \ \ \ _ \ \ / _ \ / _ / ”给出。
输出
按以下格式输出:
AK
L1,L2,…,Lk
在第一行,打印出洪水区域的总面积A。
在第二行,打印出洪水区域的个数K和每个区域的面积Li(从左到右)。
约束
1 ≤ length of the string ≤ 20000
AC代码如下:
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define p pair<char,int>
int count=0;
int sum=0;
int main()
{
string a;
p b[20000];
int n=0,c[100000]={},t=0;
cin>>a;
for(int i=0;i<a.size();i++)
{
if(a[i]!='/'&&a[i]!='_')
{
n--;
}
b[i]=make_pair(a[i],n);
if(a[i]=='/')
{
n++;
}
}
for(int i=0;i<a.size();i++)
{
if(a[i]!='/'&&a[i]!='_')
{
for(int j=i;j<a.size();j++)
{
if(a[j]=='/'&&b[j].second==b[i].second)
{
if(i>=t)
{
t=0;
count++;
}
c[count]+=j-i;
sum+=j-i;
if(j>t)
{
t=j;
}
break;
}
}
}
}
cout<<sum<<endl<<count;
for(int i=1;i<count+1;i++)
cout<<" "<<c[i];
cout<<endl;
system("pause");
return 0;
}

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。
更多推荐
所有评论(0)