正规网站备案代理,网站怎么创建论坛,什么语言做网站简单,用python做的网站多吗题目大意#xff1a;
n个人是朋友#xff0c;他们坐在一排去看电影#xff0c;相邻的最多三个人可以吃同一桶爆米花。每个人都想迟到爆米花#xff0c;问最少需要几桶爆米花#xff1f;
输入#xff1a;一个数组#xff0c;代表这n个人每个人选择的座位号。
输出
n个人是朋友他们坐在一排去看电影相邻的最多三个人可以吃同一桶爆米花。每个人都想迟到爆米花问最少需要几桶爆米花
输入一个数组代表这n个人每个人选择的座位号。
输出最少几桶爆米花
数据范围0n1000a[i]1000
解题报告
一题多解。这题是模拟但是有无数种模拟的方式我看到数据范围第一反应就是如下的模拟方式
新建一个数组保存每个位置上是否有人坐。然后从小到大遍历这个数组维护答案就可以了。
注意写的时候不能【当前位置cur有人则直接考虑cur3的位置】因为如果是【有无有】这种情况其实是应该买两桶爆米花的。
再就是一些细节问题比如while循环结束的时候cur得到的是可行的最后一个位置还是可行解的下一个位置。
时间复杂度O(n)。
思考如果这题数据范围改成n1e5, a[i]1e9那就不能做什么做了。应该是对原数组排序然后再遍历。复杂度O(nlogn)可解。
AC代码
#includeiostream
#includevector
#includequeue
using namespace std;int checkNeighboring(std::vectorint seatNumbers) {int maxx 0;for(int i 0; iseatNumbers.size(); i) {maxx std::max(seatNumbers[i], maxx);}std::vectorbool vv(maxx 1, false);for(int i 0; iseatNumbers.size(); i) {vv[seatNumbers[i]] true;}int cur 0;int ans 0;while(cur maxx) {if(vv[cur] true) {ans ;int up std::min(cur2, maxx);while(cur up vv[cur]) cur ;cur--;}cur 1;}return ans;
}int main()
{vectorint t1;t1.push_back(1);t1.push_back(2);t1.push_back(3);t1.push_back(4);t1.push_back(10);cout checkNeighboring(t1) endl; vectorint t2;t2.push_back(1);t2.push_back(3);t2.push_back(4);t2.push_back(7);t2.push_back(8);t2.push_back(10);cout checkNeighboring(t2) endl;vectorint t3;t3.push_back(4);t3.push_back(8);t3.push_back(7);t3.push_back(5);t3.push_back(6);cout checkNeighboring(t3) endl;return 0;
}
