3332783_wa.cpp

部分PKU上的源码

#include<iostream>
#include <algorithm>
using namespace std;
struct wall
{ int b,e;
};
int t,n,k,test,temp1,temp2,result,w1[101],w2[101],i,j,re;
wall x[101];
int compare1 (const int & a,const int & b)
{
	return a<b;
}

int get()
{
	result=0;
	for(i=0;i<101;i++) w1[i]=0,w2[i]=0;
	for(i=0;i<n;i++) 
	{
		for(j=0;j<result;j++)
		{
			if(w1[j]<x[i].b) {w1[j]=x[i].e;w2[j]++;break;}
		}
		if(j==result) {result++;w1[result-1]=x[i].e;w2[result-1]++;}

	}
	if(result<=k) return 0;
	else 
	{
		partial_sort(w2,w2+(result-k),w2+result,compare1);
		re=0;
		for(i=0;i<(result-k);i++) re+=w2[i];
		return re;
	}
}

int compare(const wall & a,const wall& b)
{
	if(a.b < b.b) return 1;
	if(a.b > b.b) return 0;
	else 
	{
		if(a.e < b.e) return 1;
		else return 0;
	}
}
int main()
{
	cin>>test;
	for(t=0;t<test;t++)
	{
		cin>>n>>k;
		for(i=0;i<n;i++)
		{
			cin>>x[i].b>>temp1>>x[i].e>>temp2;
		}
		sort(x,x+n,compare);
		cout<<get();
		if(t!=test-1) cout<<endl;
	}
	return 1;
}