[CSP-S模擬測試]:d(貪心+樹狀數組)

題目傳送門(內部題65)


輸入格式

第一行,一個自然數$T$,代表數據組數。
對于每組數據:
第一行,一個正整數$n$,一個自然數$m$。
接下來$n$行,每行兩個正整數,$a_i,b_i$。


輸出格式

對于每組數據,輸出一行,一個整數,代表答案。


樣例

樣例輸入:

3
2 0
5 10
5 5
2 1
1 1
2 2
3 1
3 5
4 4
5 3

樣例輸出:

25
4
12


數據范圍與提示

保證$0\leqslant m<n,a_i,b_i\leqslant 10^5$。


題解

題目并不難,考慮貪心,顯然把$m$都用完一定不劣。

先將所有矩形按照$a_i$為第一維$b_i$為第二維排序,先將最后$m$個刪去,將$b_i$加入樹狀數組,然后往前掃,不斷改變策略,更新答案就好了。

時間復雜度:$\Theta(\sum n\log \sum n)$。

期望得分:$100$分。

實際得分:$100$分。


代碼時刻

#include<bits/stdc++.h>
using namespace std;
struct rec{int a,b;}e[100001];
int n,m;
int minb,maxb;
bool vis[100001];
int tr[100001];
long long ans;
bool cmp(rec a,rec b){return a.a==b.a?a.b<b.b:a.a<b.a;}
void pre_work()
{
	memset(tr,0,sizeof(tr));
	memset(vis,0,sizeof(vis));
	minb=0x3f3f3f3f;ans=maxb=0;
}
int lowbit(int x){return x&-x;}
void add(int x)
{
	for(int i=x;i<=maxb;i+=lowbit(i))
	tr[i]++;
}
int ask(int x)
{
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=tr[i];
	return res;
}
int main()
{
	int T;scanf("%d",&T);
	if(!T)return 0;
	while(T--)
	{
		pre_work();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&e[i].a,&e[i].b);
			vis[e[i].b]=1;maxb=max(maxb,e[i].b);
		}
		sort(e+1,e+n+1,cmp);
		for(int i=n;i>m+1;i--)
		{
			add(e[i].b);
			minb=min(minb,e[i].b);
		}
		minb=min(minb,e[m+1].b);
		for(int i=m+1;i;i--)
		{
			add(e[i].b);
			if(e[i].a==e[i-1].a)continue;
			while(ask(minb)<m-i+2)minb++;
			while(!vis[minb])minb++;
			ans=max(ans,1LL*e[i].a*minb);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

rp++

posted @ 2019-10-12 10:08  HEOI-動動  閱讀(32)  評論(0編輯  收藏
七乐彩2011年走势图南方双彩