大家一起做训练 第二场 E Cottage Village
2024-10-21 20:24:35
题目来源:CodeForce #15 A
现在有 n 间正方形的房子,其中心点分布在 X轴 上,现在我需要新建一间边长为 t 的房子,要求新房子至少和一间房子相邻,但是不能和其他房子重合。请输出我有多少个位置可以选。
先分析一下:
因为现在要建一间边长为 t 的房子,而且要有一间房子与之相邻。所以,只有两种可能:第一种,在两端头。第二种,两间房子之间的间隔>= t。
分析完之后,做法已经是显而易见的了。首先,最少能建2间房子(在两端头)。然后就是遍历所有中心点,来计算房子间的距离,来判断能不能建房子。特别的,如果距离=t,只有一种方法。如果>t那么有两种。
时间效率:O( n * logn),主要用在排序上。
附AC代码:
1: #include <stdio.h>
2: #include <iostream>
3: #include <math.h>
4: #include <stdlib.h>
5: #include <string.h>
6: #include <algorithm>
7: #include <string>
8: #include <vector>
9: using namespace std;
10:
11: int t, n, pri[29], res[29], tmp[29], sum = 0;
12:
13: void dfs(int id)
14: {
15: if (id > n)
16: {
17: int m = 0;
18: for (int i = 1; i <= n; i++)
19: if (tmp[i])
20: m += pri[i];
21: if (m > sum && m <= t)
22: {
23: sum = m;
24: for (int i = 1; i <= n; i++)
25: res[i] = tmp[i];
26: }
27: return;
28: }
29: else
30: {
31: tmp[id] = 1;
32: dp(id+1);
33: tmp[id] = 0;
34: dp(id+1);
35: return;
36: }
37: }
38:
39: int main()
40: {
41: while (~scanf("%d%d", &t, &n))
42: {
43: memset(res, 0, sizeof(res));
44: memset(tmp, 0, sizeof(tmp));
45: memset(pri, 0, sizeof(pri));
46: sum = 0;
47: for (int i = 1; i <= n; i++)
48: scanf("%d", &pri[i]);
49: dfs(1);
50: for (int i = 1; i <= n; i++)
51: if (res[i])
52: printf("%d ", pri[i]);
53: printf("sum:%d\n", sum);
54: }
55: }
最新文章
- python easy_install pip django
- Stanford大学机器学习公开课(四):牛顿法、指数分布族、广义线性模型
- 走着官方的教程入门Material Design(一)
- iOS Android图标生成器PHP
- iOS网页开发技术总结
- jquery点击改变图片src源码并toggle
- github 开源项目
- maltab几个常见的问题
- dedecms修改templets为别的名字
- C# XML 根级别上的数据无效
- trangleProble switch方法 java
- [转载] 树莓派读取温湿度传感器DHT11
- javaScript函数提升及作用域
- IO模型、线程模型
- 最全面的Redis命令行查阅手册(收藏查看)
- 对数log
- Java 日志
- WPF 的 数据源属性 和 数据源
- python之爬虫_模块
- C. Mail Stamps---cf29c(离散化,图)
热门文章
- angular5 ng-content使用方法
- 20170719xlVBASmartIndent
- 安卓出现Invalid layout of java.lang.String at value
- Python基础--Python简介和入门
- 10046 event 知多少
- [Leetcode] Unique binary search trees 唯一二叉搜索树
- redis 处理命令的过程
- 改变进程的优先级,nice,getpriority,setpriority
- jconsole工具使用----jvm内存泄漏问题
- git commit steps(1)