code forces 996BWorld Cup
1 second
256 megabytes
standard input
standard output
Allen wants to enter a fan zone that occupies a round square and has nn entrances.
There already is a queue of aiai people in front of the ii-th entrance. Each entrance allows one person from its queue to enter the fan zone in one minute.
Allen uses the following strategy to enter the fan zone:
- Initially he stands in the end of the queue in front of the first entrance.
- Each minute, if he is not allowed into the fan zone during the minute (meaning he is not the first in the queue), he leaves the current queue and stands in the end of the queue of the next entrance (or the first entrance if he leaves the last entrance).
Determine the entrance through which Allen will finally enter the fan zone.
The first line contains a single integer nn (2≤n≤1052≤n≤105) — the number of entrances.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109) — the number of people in queues. These numbers do not include Allen.
Print a single integer — the number of entrance that Allen will use.
4
2 3 2 0
3
2
10 10
1
6
5 2 6 5 7 4
6
In the first example the number of people (not including Allen) changes as follows: [2,3,2,0]→[1,2,1,0]→[0,1,0,0][2,3,2,0]→[1,2,1,0]→[0,1,0,0]. The number in bold is the queue Alles stands in. We see that he will enter the fan zone through the third entrance.
In the second example the number of people (not including Allen) changes as follows:[10,10]→[9,9]→[8,8]→[7,7]→[6,6]→[5,5]→[4,4]→[3,3]→[2,2]→[1,1]→[0,0][10,10]→[9,9]→[8,8]→[7,7]→[6,6]→[5,5]→[4,4]→[3,3]→[2,2]→[1,1]→[0,0].
In the third example the number of people (not including Allen) changes as follows:[5,2,6,5,7,4]→[4,1,5,4,6,3]→[3,0,4,3,5,2]→[2,0,3,2,4,1]→[1,0,2,1,3,0]→[0,0,1,0,2,0][5,2,6,5,7,4]→[4,1,5,4,6,3]→[3,0,4,3,5,2]→[2,0,3,2,4,1]→[1,0,2,1,3,0]→[0,0,1,0,2,0].
题解:这个题是一个模拟题,问有n个队伍,你不想排队,每次只能走到下一个队伍
请问你在哪个队伍可以不用排队
首先我们可以想到,第一遍走的情况,从头到尾,
那么第一遍模拟就可以是 for(int i =0 ;i<n;i++) a[i]-=i;
这里就有问题了 如果第一遍走不完怎么办 继续从最后一个走到第一个 ,这是一个类似于环一样的
可是我们第一遍模拟的时候只考虑了走后面的情况,走过前面的需要还原,所以我们这里倒着减一下,
使得走一遍后保证每个队伍都走了n个单位长度
那么这里有问题了 如果n特别小但是a[i]特别大呢
我们有两个优化的地方
1.找出a[i]的最小值,每个都减去min
2.由于a[i]<1e9,n<=1e5,那么在n的循环里面循环20次就可以满足至少出现一个空队列的情况
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn= 1e5+;
const int INF = 0x3f3f3f3f;
ll a[maxn];
int main() {
int n;
while(~scanf("%d",&n)) {
int ans=;
int minn=INF;
for(int i=; i<n; i++) {
scanf("%lld",&a[i]);
if(a[i]<minn) minn=a[i];
}
int cnt=minn/n;
//优化1
for(int i=; i<n ; i++) {
a[i]-=cnt*n;
}
//优化2
for(int d=; d<=; d++) {
for(int i=; i<n; i++) {
a[i]-=i;
if(a[i]<=) {
cout<<i+<<endl;
return ;
}
}
//还原
for(int i=n-;i>=;i--) {
a[i] -= n - i;
}
}
}
return ;
}
最新文章
- Json数据处理
- input输入框,回车激活按钮事件代码
- GridView数据源绑定的一个小问题
- 在idea中如何添加log日志
- IOS - UIImage
- 关于 CentOS 自启动(服务、脚本)
- 关于蓝桥杯嵌入式STM32的一点收获
- 故障公告:IIS应用程序池停止工作造成博客站点无法访问
- 读外部存储的权限READ_EXTERNAL_STORAGE
- 20175315 实验二《Java面向对象程序设计》实验报告
- vuex2中使用mapGetters/mapActions报错解决方法
- vb.net 使用ip查詢(Host Name)(WorkGroup Name)(MAC Address)-運用cmd及nbtstat命令
- django如何语法高亮模块
- 剑指offer例题——二进制中1的个数
- 4826: [Hnoi2017]影魔
- 字符串--C++系列
- 【Spring Boot&;&;Spring Cloud系列】Spring Boot初识
- Android图表开发——AChartEngine
- JMeter学习笔记--详解JMeter定时器
- Android TextView实现跑马灯