作为本题一血,我自然要发波题解
题意:
Indeed公司里有N名员工。职员i (1≤i≤N)在时刻 Si 上班,在时刻 Ti下班。各职员,对自己在办公室的期间上班了的职员听"How are you?"。即,Si < Sj < Ti 满足的时候,职员i对职员j说"How are you?"。你决定计算每个员工对几个人说"How are you?"。
题很简单,就是输出第i人与多少人符合其上班时间在i的上班下班的范围之间(看看样例就懂了)
所以用一个n方的代码就完了
BUT!!!
n的范围是(1 ≦ N ≦ 1e6) ,不优化怎么能行!
SO!!!
作为蒟蒻的我只能猥琐了(见题解)
#include<stdio.h> #pragma GCC optimize(3,"Ofast","inline")//用猥琐的O3优化 int s[100005],t[100005],time[200005];//time记录某上班时间出现的次数 inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } int main() { int n=read(),ans; for(register int i=1; i<=n; ++i) { s[i]=read(),t[i]=read(); time[s[i]]++; } for(register int i=1; i<=n; ++i) { ans=0; for(register int j=s[i]+1; j<t[i]; ++j) { ans+=time[j]; } printf("%d\n",ans); } return 0; }
如此简单的代码就不说思路了