Codeforces Round#451 Div.2 D(时间问题)
文章目录
题目:D. Alarm Clock
Every evening Vitalya sets n alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer ai — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute.
Vitalya will definitely wake up if during some m consecutive minutes at least k alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time.
Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on.
Input
First line contains three integers n, m and k (1 ≤ k ≤ n ≤ 2·105, 1 ≤ m ≤ 106) — number of alarm clocks, and conditions of Vitalya's waking up.
Second line contains sequence of distinct integers a1, a2, ..., an (1 ≤ ai ≤ 106) in which ai equals minute on which i-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for 106 minutes.
Output
Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.
数据
Examples
Input
3 3 2
3 5 1
Output
1
Input
5 10 3
12 8 18 25 1
Output
0
Input
7 7 2
7 3 4 1 6 5 2
Output
6
Input
2 2 2
1 3
Output
0
提示:In first example Vitalya should turn off first alarm clock which rings at minute 3.
In second example Vitalya shouldn't turn off any alarm clock because there are no interval of 10 consequence minutes in which 3 alarm clocks will ring.
In third example Vitalya should turn off any 6 alarm clocks.
题目大意:每个闹钟只会响一分钟,一共有n个闹钟,被叫醒的情况是在m分钟内有至少k个闹钟响过。题目让求的结果是,为了让保证不被叫醒,至少关掉的闹钟的个数;输入的第二行会n个闹钟会响的时间(以后在每次读完题目之后找出关键变量,再找找有没有什么式子,再结合数据,之后再结合提示);
起初做的思路:先确定闹钟都只会响一分钟而已,所以题目就变成了在m分钟内超出k个闹钟这个范围的数量,又因为是至少的问题,所以每次关比较后面的闹钟就可以了,比如,k=4个闹钟,如果有第5个闹钟会响,则会关掉第5个;还有因为n个闹钟响的时间不是按大小输入的,所以用sort排序(为了减少时间);
之后再利用标记变量进行循环统计是否在m范围内达到k个,一旦达到k,后面的那些都把值用0给覆盖,这里运用的小技巧就是将已经处理的数组元素让其值给变成一个专门的值(一般是0或者一定不会出现在数组元素中的值),然后在每次进行循环处理的时候把这种专门的值给跳过;
错误原因:超时,因为在判断m范围内是否超过k个的时候,两层循环,又因为此时题目中有大数据,所以就会超时了;
看了别人的之后的改进:发现,可以专门再建立一个数组用来存其闹钟响的时间,例s[a[i]]=1;这样a[i]本身作为下标之后,这个s[]得数组就无需排序,而直接按下标进行就可以了,并且1是为了表示这个地方有闹钟,且时间为1;(这个思路的产生就源于为了不再进行排序,而直接再建立一个数组,利用下标进行进一步的操作,学会利用新数组的下标直接表示顺序,类似这题);关哪个闹钟的思路一样,就是关掉后面超出的那几个,但是在判断是否在m分钟范围内时,没有利用循环,而是专门设置一个表明其起始位置,就是类似区间长度一样的感觉,有一个m长度的区间,一旦超了就往前移动,然后边移动边统计其内部闹钟数,刚好超过的将其关掉;(这个方法如果要总结成一个通用的方法就是对于有一个区间或者称为范围的题目,要求其内部区间怎么怎么样,而且这个总的长度是已知的(一般是数组),这样就可以将其区间进行移动,而不是利用循环在数组中找合适,这就是数学中的移动区间的思路);
我的超时代码:
include<stdio.h>
include<algorithm>
using namespace std;
int a[200000];
int main()
{
int n,m,k,i,j,tag,temp,s,x,t;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
temp=0;
for(i=0;i<n;i++)
{
if(a[i]==0)
continue;
tag=1;
s=a[i]+m-1;
for(j=i+1;j<n;j++)
{
if(a[j]<=s)
tag++;
else
break;
}
if(tag>=k)
{
temp+=tag-k+1;
for(x=j-1;x>=j-(tag-k+1);x--)
a[x]=0;
}
}
printf("%d\n",temp);
return 0;
}
别人那个思路的代码:
include<stdio.h>
int a[200001],index[1000005]={0};
int main()
{
int n,i,m,k,l=0,r=0,count=0,ans=0;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
index[a[i]]=1;
}
while(r<1000003)
{
if(index[r]==1)
{
count++;
}
if(count==k && r-l<m)
{
index[r]=0;
count--;
ans++;
}
if(r-l==m-1)
{
if(index[l]==1)
count--;
l++;
}
r++;
}
printf("%d\n",ans);
return 0;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论