目录
题目 - 开灯
题目描述
在一条无限长的路上，有一排无限长的路灯，编号为 1 , 2 , 3 , 4 , ······。
每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。
在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：
指定两个数， a , t （ a 为实数， t 为正整数）。将编号为 ⌊a⌋ , ⌊2×a⌋ , ⌊3×a⌋ , … , ⌊t×a⌋ 的灯的开关各按一次。其中 ⌊k⌋ 表示实数 k 的整数部分。
在小明进行了 n 次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。
幸好，小明还记得之前的 n 次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？
输入格式
第一行一个正整数 n ，表示 n 次操作。
接下来有 n 行，每行两个数， ai , ti 。其中 ai 是实数，小数点后一定有 6 位， ti 是正整数。
输出格式
仅一个正整数，那盏开着的灯的编号。
样例 #1
样例输入 #1
3
1.618034 13
2.618034 7
1.000000 21
样例输出 #1
20
提示
记 T 为对 ti 求和的值，
- 对于 30% 的数据，满足 T ＜ 1000 ；
- 对于 80% 的数据，满足 T ＜ 200000 ；
- 对于 100% 的数据，满足 T ＜ 2000000 ；
- 对于 100% 的数据，满足 n ＜ 5000 ， 1 ＜ ai ＜1000 ， 1 ＜ ti ＜ T 。
数据保证，在经过 n 次操作后，有且只有一盏灯是开的，不必判错。而且对于所有的 i 来说， ti * ai 的最大值不超过 2000000 。
AC CODE
思路
- 题目的数据量 ＞ 2e6 ，使用数组（array）是装不下的，而且最后遍历数组的时间复杂度也非常高
- 因此总体思路是，使用某个结构，标记每次操作后出现变化的灯
使用 Map
- 每次进行 map.find 操作，如果该灯已被标记，则翻转灯的状态，如果该灯未被标记，则将其打上 "已被点亮" 的标记
- 遍历 map 中的元素，其中标记为 "点亮" 的灯为结果
使用 Set
- 设定点亮的灯被放入 set 中，那么每次对被选中的灯进行 set.find 操作，如果 find 成功，表示灯需要被熄灭，则进行 set.erase 操作，如果 find 失败，则表示该灯需要被点亮，进行 set.insert 操作
- 最后 set 中只会剩下被点亮的灯，在进行结果遍历时会更快
AC CODE
C++
#include <iostream>
#include <set>
using namespace std;
int main()
{
int t;
cin >> t;
set<int> opare_set;
while (t != 0)
{
double num;
int k;
cin >> num >> k;
for (int i = 1; i <= k; i++)
{
int temp = (int)(1.0 * num * i);
if (opare_set.find(temp) == opare_set.end())
{
opare_set.insert(temp);
}
else
{
opare_set.erase(temp);
}
}
t--;
}
for (auto it : opare_set) {
cout << it << endl;
}
return 0;
}
说明
使用 Map 做数据标记，会出现 TEL
-
因为 set 的查找效率更高，它的增删改查时间复杂度都为 logN
set 会对集合中的元素进行排序，set 的底层数据结构是红黑树（平衡二叉树），因此查找效率更高
-
最后 set 中只会剩下被点亮的灯，在进行结果遍历时会更快
-
和 Java 中 Set 容器的底层实现类似，Set 是一组只用 key 值的 Map 结构
在此附上使用 Map 之后 TEL 的代码
#include<bits/stdc++.h>
using namespace std;
int lowerN(double n) // 向下取整函数
{
return floor(n);
}
int main()
{
int k;
cin>>k;
map <int,bool> flag; // map记录被改变状态的灯
for(int h=0;h<k;h++)
{
double a;
int t;
cin>>a>>t;
for(int i=1;i<=t;i++)
{
int temp=1.0*a*i;
temp=lowerN(temp);
//迭代器 记录灯是否改变状态
map <int,bool>::iterator iterflag;
iterflag=flag.find(temp);
if(iterflag==flag.end())
{
flag.insert(pair<int,bool>(temp,true));
}
else
{
flag[temp]=!flag[temp];
}
}
}
int anser;
map <int,bool>::iterator iteranser;
for(iteranser=flag.begin();iteranser!=flag.end();iteranser++)
{
if(iteranser->second==true)
{
anser=iteranser->first;
break;
}
}
cout<<anser<<endl;
return 0;
}
向下取整
- 在 C/C++/Java 中，使用
(int)等进行强制类型转换，计算机会采用丢失精度的方式进行强转，得到的结果就是保留了数值的整数位 - 可以使用
<math.h>头文件中的 floor 函数完成取整操作
<math.h> 中常用的函数
参考自以下文章
取整函数
- floor(double x)：向下取整函数，标准定义为取比 x 小的最大整数，因此
floor(-2.3) = -3 - ceil(double x)：向上取整函数，标准定义为取比 x 大的最小整数，因此
ceil(-2.3) = -2
取绝对值
- abs(int x)：对整型取绝对值
- fabs(double x)：对浮点型取绝对值
- labs(long x)：对长整型取绝对值
四舍五入
- round(double x)：四舍五入函数
运算
- pow(double x, double y)：幂函数，求 x 的 y 次方，当 y = 0.5，就是对 x 求平方根
- log(double x)：对数函数，求以 e 为底数 x 的对数
- sqrt(double x)：对 x 开平方函数，得到一个大于 0 的结果