AOJ2211 Stray Cats, Run...

えさばこが混雑しないように餌箱の位置を設定する問題。

ちょっと考えると、
①全部の餌箱がある場合を考える
②その中で一番混雑しているえさばこを取り除いて同じことをする
③それらをくりかえし、その過程で出た結果の最小値をもとめる

というグリーディーでいけることがわかる（ある場合から、一番混雑しているえさばこを取り除かないならば、一番混雑している餌箱に集まっている猫の数は減ることはないため）

それにしか見えなかったが、正解者が少なく実は落とし穴があるのかと思ったが、見つからないのでとりあえず実装。std::setとかつかってみる。O(n^2)に落とせそうな気がしたけど、まあO(n^2log n)でも通りそうなので、それで書く。

バグとってsubmit、1発AC。

#include<stdio.h>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	for(;;)
	{
		int cat,fee;
		scanf("%d%d",&cat,&fee);
		if(cat==0&&fee==0)
		{
			break;
		}
		vector<pair<int,int> >cats;
		for(int i=0;i<cat;i++)
		{
			int za,zb,zc;
			scanf("%d%d%d",&za,&zb,&zc);
			cats.push_back(make_pair(za,zc));
		}
		set<int>se;
		set<int>::iterator ite;
		vector<int>vec;
		for(int j=0;j<fee;j++)
		{
			int zan;
			scanf("%d",&zan);
			se.insert(zan);
			vec.push_back(zan);
		}
		sort(vec.begin(),vec.end());
		vector<int>damy;
		for(int l=0;l<fee;l++)
		{
			damy.push_back(0);
		}
		int mini=2000000000;
		for(int k=0;k<fee;k++)
		{
			ite=se.begin();
			vector<int>smp=damy;
			for(int m=0;m<cat;m++)
			{
				ite=se.lower_bound(cats[m].first);
				int end;
				if(ite==se.end())
				{
					ite--;
				}
				end=*ite;
				int beg;
				if(ite==se.begin())
				{
					ite++;
				}
				ite--;
				beg=*ite;
				if(end-cats[m].first>=cats[m].first-beg)
				{
					int low=lower_bound(vec.begin(),vec.end(),beg)-vec.begin();
					smp[low]+=cats[m].second;
				}
				else
				{
					int low=lower_bound(vec.begin(),vec.end(),end)-vec.begin();
					smp[low]+=cats[m].second;
				}
			}
			int maxin=0,nn;
			for(int n=0;n<fee;n++)
			{
				if(maxin<smp[n])
				{
					maxin=smp[n];
					nn=vec[n];
				}
			}
			se.erase(nn);
			mini=min(maxin,mini);
		}
		printf("%d\n",mini);
	}
}