借今年浙江省赛的题练练手。
首先,由题意知,A与B发信息,当A与B连续互相发信息m天时,好感度point+1.。输入有A向B发信息的天数与B向A发信息的起止天数,具体格式看题。n是指在求第n天的point。
根据其给出了起止天数可以把它当做求公共区间的问题。自定义结构体有start和endd属性代表起止天数,分为A,B两个数组,按start从小到大排序,while语句比较公共区间
AC代码 Memory 184 Time 0
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100+20;
int n,m,x,y;
struct Node
{
int start,endd;
}A[maxn],B[maxn];
int cmp(struct Node s1,struct Node s2)
{
return s1.start<s2.start;
}
int main()
{
int test;
scanf("%d",&test);
for(int i=0;i<test;i++)
{
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int j=1;j<=x;j++) scanf("%d%d",&A[j].start,&A[j].endd);
for(int j=1;j<=y;j++) scanf("%d%d",&B[j].start,&B[j].endd);
sort(A+1,A+1+x,cmp);
sort(B+1,B+1+y,cmp);
int ans=0,j=1,k=1;
while(k<=y && j<=x)
{
int a,b;
if(B[k].start>A[j].endd) { j++; continue; }
if(B[k].endd<A[j].start) { k++; continue; }
a=max(B[k].start,A[j].start);
b=min(B[k].endd,A[j].endd);
if(a>n || b>n) break;
int date=b-a+1;
int point=date+1-m;
if(point>=1) ans+=point;
if(A[j].endd<B[k].endd) j++;
else if(A[j].endd==B[k].endd) { j++; k++;}
else k++;
}
printf("%d\n",ans);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)