北大ACM 第1727怎样做呀

来源:百度知道 编辑:UC知道 时间:2024/05/18 12:51:43
我现在刚开始做ACM,想问一下北大ACM第1727的分析

#include <stdio.h>
#include <algorithm>

struct event
{
int t;
int x;
};

event all[100001];
int n,m;
int maxt;
int mint;

int cmp(const void *a,const void *b)
{
return (*(event*)a).x-(*(event*)b).x;
}

int greed(int maxt)
{
int mi,mx;
int nmi,nmx;
int bo=0;
int res=0;
for(int i=0;i<n;i++)
{
if(!bo)
{
mi=maxt-all[i].t+all[i].x;
mx=all[i].t-maxt+all[i].x;
res++;bo=1;
if(res>m) return 0;
}
else
{
nmi=maxt-all[i].t+all[i].x;
nmx=all[i].t-maxt+all[i].x;
if(nmi>mi) mi=nmi;
if(nmx<mx) mx=nmx;
if(mx<mi)
{
bo=0;i--;
}
}