Segments CodeForces 909B (找规律)
Description
You are given an integer N. Consider all possible segments (线段,划分)on the coordinate axis with endpoints at integer points with coordinates between 0 and N, inclusive; there will be of them.
You want to draw these segments in several layers so that in each layer the segments don't overlap(重叠) (they might touch at the endpoints though). You can not move the segments to a different location on the coordinate axis.
Find the minimal number of layers(层次) you have to use for the given N.
Input
The only input line contains a single integer N (1 ≤ N ≤ 100).
Output
Output a single integer - the minimal number of layers required to draw the segments for the given N.
Sample Input
2
2
3
4
4
6
Hint
As an example, here are the segments and their optimal arrangement(最优排列) into layers for N = 4.
#include <stdio.h>
using namespace std;
int main()
{
int n,k,i,a[];
a[]=;
a[]=;
a[]=;
for(i=;i<=;i++)
{
k=i*(i+)/;///总的子线段数
a[i]=k-a[i-];
}
while(~scanf("%d",&n))
{
printf("%d\n",a[n]);
}
return ;
}
但其实也可以这样想,最后得到的层次数是原来长度为n的线段的若干条可能还会有部分,又因为每一层的线段都是子串在坐标轴上不动拼接得来的,那么我们将线段分成一个个的坐标上的点,那么出现次数最多的那个点的次数就是层次数!!!
#include<stdio.h>
#include<algorithm>
using namespace std;
int vis[];
int main()
{
int n,j,i,k,ans;
ans=;
scanf("%d",&n);
for(i=; i<=n; i++)
{
for(j=i; j<=n; j++)///划分子段
{
for(k=i; k<=j; k++)///将子段拆成一个个的点
{
vis[k]++;
}
}
}
for(i=; i<=; i++)
{
ans=max(ans,vis[i]);
}
printf("%d\n",ans);
return ;
}
最新文章
- ViewPager +Fragment 滑动游标
- 抄书 Copying Books UVa 714
- java 构造方法
- Android的构造器
- cuffdiff 和 edgeR 对差异表达基因的描述
- 【转】Php+ajax+jsonp解决ajax跨域问题
- c# 事件为何要继承EventArgs
- C#实现发送邮件——核心部分代码
- C++中的快速排序(使用vector和数组的不同)
- UVA 1001 Say Cheese 奶酪里的老鼠(最短路,floyd)
- sql基本语法:
- C#的装箱和拆箱
- 无锁队列--基于linuxkfifo实现
- Linux监控工具vmstat命令详解
- 载入DLL中的图片资源生成Skia中的SkBitmap对象
- 模拟Vue之数据驱动
- Dynamic Web Module 3.0 requires Java 1.6 or newer.的解决
- SpringMVC源码分析--容器初始化(三)HttpServletBean
- Space Invaders 太空侵略者
- nfs环境搭建报错clnt_create: RPC: Program not registered