739
HDU 4302 MAP应用
题意：有一个动物在一条长为L的直线上，每次吃离他最近的东西，东西不断刷新，它也不短在吃，N次操作，问他走了多少距离，如有前后距离相同按照上一次走的方向吃。
这题队友map过的，我map不熟，写了一下就当熟悉Map了，因为map内部有序，所以查询当前位置最近的两个点（一前一后），再定义一个方向标记就可以了。
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
const int oo=1000000;
int main()
{
map<int,int>mymap;
int t,l,n,co,a,b,ca=0;
map<int,int>::iterator it1,it2;
scanf("%d",&t);
while(t--)
{
mymap.clear();
mymap[oo]=1,mymap[-oo]=1;
scanf("%d%d",&l,&n);
co=0;
int ans=0,dir;
while(n--)
{
scanf("%d",&a);
if(a)
{
it1=mymap.lower_bound(co);
if(it1->first==co)
{
it1->second--;
if(it1->second==0) mymap.erase(it1);
}
else
{
it1--;
it2=mymap.upper_bound(co);
if(it1->first==-oo&&it2->first==oo) continue;
if(co-it1->first==it2->first-co)
{
if(dir==1)
{
it2->second--;
ans+=it2->first-co;
co=it2->first;
if(it2->second==0) mymap.erase(it2);
}
else
{
it1->second--;
ans+=co-it1->first;
co=it1->first;
if(it1->second==0) mymap.erase(it1);
}
}
else if(it2->first-co<co-it1->first)
{
dir=1;
ans+=it2->first-co;
co=it2->first;
it2->second--;
if(it2->second==0) mymap.erase(it2);
}
else
{
dir=0;
ans+=co-it1->first;
co=it1->first;
it1->second--;
if(it1->second==0) mymap.erase(it1);
}
}
}
else
scanf("%d",&b),mymap[b]++;
}
printf("Case %d: %d\n",++ca,ans);
}
return 0;
}
最后更新：2017-04-03 18:52:02