第四天
先写个今日总结：
二分查找，不要瞎搞。
本来还是二分查找的题目，想试着暴力破解。后来发现不行，超时间了。
题目来源
题目描述
蒜头是个爱学习的孩子，他总喜欢在生活中做一些小实验，这次蒜头想研究一下光合作用。
蒜头的实验材料有如下几样：神奇的种子，普通的纸箱和一些光源。一开始，蒜头将种子均匀的种在了箱子底部，你可以将其看成 X 轴，种子的位置为 X 轴上的点。然后蒜头用纸板将箱子盖住，并在纸板上安装了一些光源（具体见图）。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在蒜头想知道当实验结束时每颗种子的高度是多少？
顶上的为光源，光源两边与顶部的夹角都为 45°，黄色部分为光照，绿色的为植物。
样例输入
2
7 1 2
4
4 4 1
1
2
3
4
样例输出
0
0
1
2
1
0
0
1
1
1
1
思路
错误思路：
本思路即暴力扫描
以test[100000]为标记数组,根据输入的n确定上限
输入T
while(T--)
输入n,m,H;
for i 从0 到 n: test[i]=0;
for i 从0 到 m:
输入 tmp
在tmp附近扫描，并判断是否在边界内，根据H进行赋值，若赋值后不大于原来数值，则不不赋值
for i 从1 到 n: 输出test[i];
该思路遇到的困难：
该思路的结果：
据估计，单组运算的时间复杂度达O(mH+2n)
即O(m*H + n)
不过还是有可能解决的，考虑好各个灯泡之间的位置关系是有可能更进一步降低时间复杂度的
错误思路代码
#include<iostream>
#include<algorithm>
using namespace std;
#define max 100010
int mark[max];//灯泡位置数组
int cmp(const void *a, const void *b)
{
return *(int *)b-*(int *)a ;
}
int main()
{
int n, m, H;
int T;
cin >> T;
int tmp;
bool status = false;//标记越界处理用
while (T--)
{
cin >> n >> m >> H;
//初始化
int test[max]={0};
for (int i = 0; i<m; ++i)
{
cin >> mark[i];
}
qsort(mark, m, sizeof(int), cmp);
for (int i = 0; i < m; ++i)
{
status = false;
tmp=mark[i];
//当可能越界
if ((tmp + H - 1>n)||(tmp-H+1<1))
{
status = true;
//扫描
for (int k = 1 - H; k < H; ++k)
{
if (tmp + k > n)break;
if (tmp + k < 1)continue;
if (H - abs(k) > test[tmp + k])test[tmp + k] = H - abs(k);
}
}
//处理越界情况后，跳过本次正常处理
if (status)continue;
//正常扫描
for (int k = 1 - H; k < H; ++k)
{
if (H - abs(k) > test[tmp + k])
test[tmp + k] = H - abs(k);
}
}
//output
for (int i = 1; i <= n; ++i)
{
cout << test[i] << endl;
}
}
return 0;
}
正确思路
以下是用二分查找的正确姿势......
参考链接
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int x[maxn];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m,h;
scanf("%d %d %d",&n,&m,&h);
for(int i=1;i<=m;i++)
{
scanf("%d",&x[i]);
}
sort(x+1,x+m+1);
for(int i=1;i<=n;i++)
{
int ans = 0;
//找到第一个大于等于i的元素，利用二分查找
int cnt = lower_bound(x+1,x+m+1,i)-x;
//当查找到的元素为第一个元素
if(cnt==1&&m!=0)
{
ans = max(ans,h-x[cnt]+i);
}
//当查找到的元素为最后一个元素
else if(cnt==m+1&&m!=0)
{
ans = max(ans,h-i+x[cnt-1]);
}
//当查找到的元素为中间部分的元素
else if(m!=0)
{
ans = max(0,max(h-i+x[cnt-1],h-x[cnt]+i));
}
printf("%d\n",ans);
}
}
return 0;
}
收获：
.
散列表习题
题目来源
题目描述：
Your task is to write a program of a simple dictionary which implements the following instructions:
- <b>insert str</b>: insert a string str in to the dictionary
- <b>find str</b>: if the distionary contains str, then print 'yes', otherwise print 'no'
Input
In the first line n, the number of instructions is given. In the following n lines, n instructions are given in the above mentioned format.
output
Print yes or no for each find instruction in a line.
Constraints
- A string consists of 'A', 'C', 'G', or 'T'
- 1 ≤ length of a string ≤ 12
- n ≤ 1000000
Sample Input 1
5
insert A
insert T
insert C
find G
find A
Sample Output 1
no
yes
思路：
书上说用散列表做，然后调皮了一下,比较了一下412 *sizeof(bool) b跟131072kb的大小关系，于是决定直接用数组标记就好了。后面补充一下散列表的做法。
代码：
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define max 16777216
bool mark[max]={false};
unsigned int find(string b)
{
unsigned int result = 0;
unsigned int tmp = 1;
unsigned int len = b.length();
for (int i = 0; i < len; ++i)
{
switch (b[i])
{
case 'A':
result += tmp * 1; break;
case 'C':
result += tmp * 2; break;
case 'G':
result += tmp * 3; break;
case 'T':
result += tmp * 4; break;
}
tmp *= 4;
}
return result;
}
int main()
{
string a="abc";
int n;
cin >> n;
if (!n)return 0;
while (n--)
{
cin >> a;
if (a == "insert")
{
cin >> a;
mark[find(a)] = true;
}
else
{
cin >> a;
if (mark[find(a)])cout << "yes" << endl;
else cout<<"no"<<endl;
}
}
return 0;
}
看了一下 差0.03s突破1s,有点悬。
