本文主要是介绍soj2166D 反垃圾邮件，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
又做了一道吴大大出的题，恩，感觉这题质量可以，测试用例也不错。粗心导致了多次wa。。。做模拟题还是功力不够啊。。。
先贴题目：
Problem D：反垃圾邮件
随着互联网的高速发展，网络通信变得十分便利，电子邮件便是渠道之一，而由此带来
的问题是，我们总会收到大量来自互联网的垃圾邮件，这是让人烦扰的一件事。
限制短时间内发送大量电子邮件，是一种有效的避免垃圾邮件泛滥的措施。这里我们只
考虑其中一个最简单的模型(实际生活中，不会被简单地采用)：对于电子邮件的发送方而言，
其任意已经发送的两封不同的邮件，若其发送时间间隔在 T内，则不存在超过 x封自发邮件
(表示自己写邮件内容)或y封转发邮件(表示转发别人的邮件)。
为方便理解，假定有N封邮件需要按时间先后顺序发送， 假设现在需要发送第M (1≤M≤N)
封邮件，虽然此前有 M-1封邮件已经尝试去发送，但可能只有一部分发送成功。记此前已发
送成功的邮件有 S 封，那么第 M 封邮件是否能够发送成功，取决于它与这 S 封邮件是否满
足反垃圾邮件限制。如果 S=0，那么第 M封邮件一定可以发送；否则，这 S封邮件里面的第
k (1≤k≤S)封发送成功的邮件与第M封邮件若满足A条件， 则遵循 B规则， 若不满足 A条件，
则第M封邮件会发送成功。
A. 两者待发送的时间间隔在时间T 内。
B. 如果第 M 封邮件发送成功，那么在第 k (1≤k≤S)封邮件和第 M 封邮件之间，如果存
在超过 x 封自发邮件或 y 封转发邮件成功发送(第 k 封和第 M 封邮件的类型也要计
算在内)，那么实际情况是第 M封邮件会发送失败，否则，这封邮件会发送成功。
输入说明
多组测试数据，每组测试数据第一行包含4个整数N, T, x, y (0≤N, T, x, y≤105)，分别表示待发
的邮件总数量，时间限制间隔，自发邮件限制数量以及转发邮件限制数量。接下来的 N行，
每行包含2 个整数pk (0≤pk≤105)和qk (qk = 1, -1)，分别表示邮件发送的时间和邮件的分类，如
果qk=1，表示邮件是自发邮件，否则，一定有 qk=-1且表示邮件是转发邮件。输入数据保证
各邮件发送的时间互不相同，pk越小表示邮件发送的优先级越高。
输出说明
对于每组测试数据，输出发送成功的邮件数量，每组测试数据占用1行。
样例输入
2 10 0 0
1 1
11 -1
2 10 1 1
1 1
12 -1
样例输出
1
2
唉必须说我做题时心态不行，当时太慌张，一看以为这题要用线段树做，虽然我基本不会线段树。。一算时间复杂度怎么都在n*n，就放弃了这道题，实际上这题只是简单的模拟。。。
方法就是，先按时间对邮件排序，再依次遍历，用两个数组保存两种邮件的数量。对于当前考察的邮件，只需要在已发送成功的邮件中二分查找刚好满足时间限制的邮件，再比较是否满足数量限制，而且只需比较这一个，因为如果找到的与当前邮件冲突，就可以直接判断当前油价不能发送，如果不冲突，那后面的也不会冲突，就这样，复杂度为n*lgn，其实看输入数据量就能大致判断需要多少复杂度的算法，这里10000，必然复杂度要小于n*lgn。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int MAX=100000+10;
int n,t,x,y,all,aa[MAX],bb[MAX];struct mail
{int time,type,index;bool operator<(mail other)const{return time<other.time;}void operator=(mail other){time=other.time,type=other.type;}
}s[MAX],ss[MAX];int bsearch(int t)
{if(all==0||ss[all-1].time<t)return -1;if(ss[0].time>=t)return 0;int front=0,rear=all-1,mid,i,j;while(front+1<rear){mid=(front+rear)/2;if(ss[mid].time<t)front=mid;elserear=mid;}return rear;
}int main()
{int i,j,typea,typeb,sea;while(scanf("%d %d %d %d",&n,&t,&x,&y)!=EOF){for(i=0;i<n;i++){scanf("%d %d",&s[i].time,&s[i].type);}sort(s,s+n);memset(aa,0,MAX*4);memset(bb,0,MAX*4);all=0;for(i=0;i<n;i++){sea=bsearch(s[i].time-t);//大于等于time-t的最小时间if(sea==-1){ss[all].index=i;ss[all++]=s[i];if(s[i].type==1){aa[i]=(i==0?1:aa[i-1]+1);bb[i]=(i==0?0:bb[i-1]);}else{aa[i]=(i==0?0:aa[i-1]);bb[i]=(i==0?1:bb[i-1]+1);}}else{typea=((s[i].type==1)?1:0);typea=((ss[sea].type==1)?(typea+1):typea);//ss写成了stypeb=((s[i].type==-1)?1:0);typeb=((ss[sea].type==-1)?(typeb+1):typeb);if(typea+aa[i-1]-aa[ss[sea].index]>x||typeb+bb[i-1]-bb[ss[sea].index]>y)//ss写成了s{aa[i]=aa[i-1],bb[i]=bb[i-1];//等号写成了==}else{ss[all].index=i;ss[all++]=s[i];if(s[i].type==1){aa[i]=aa[i-1]+1;bb[i]=bb[i-1];}else{aa[i]=aa[i-1];bb[i]=bb[i-1]+1;}}}}printf("%d\n",all);}return 0;
}
这篇关于soj2166D 反垃圾邮件的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
