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