$ 2019 $ 暑期刷题记录 $ 2 $ （基本算法专题）
$ by~~wch $
$ BZOJ~1958~Strange~Towers~of~Hanoi $ （动态规划，递推）
题目大意：
求有 $ n $ 个盘子和 $ 4 $ 座塔的汉诺塔问题。
$ solotion: $
首先需要参考一下三座塔的汉诺塔问题： $ g[i]=2*g[i-1]+1 $然后我们将四座塔转换为三座塔问题：将前 $ i $ 个盘子一道2号塔，剩下的 $ n-i $ 个为三汉诺问题移到4号塔，再将前 $ i $ 个用四汉诺塔问题移到4号塔。$ f[n]=min_{1\leq i < n}{2*f[i]+g[n-i]} $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n=12;
int g[13],f[13];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
for(rg i=1;i<=n;++i) g[i]=2*g[i-1]+1;
for(rg i=1;i<=n;++i){
f[i]=1<<30;
for(rg j=0;j<i;++j)
f[i]=min(f[i],f[j]*2+g[i-j]);
}
for(rg i=1;i<=n;++i)
printf("%d\n",f[i]);
return 0;
}
$ BZOJ ~1218 ~ $ 激光炸弹（二维前缀和）
$ solotion: $
比较明显的二维前缀和问题就是这一题有点卡常，如果暴力转一维前缀和会超时我们需要自己寻找每个点前缀和的关系：$ s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j] $
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
int n,m,ans,a,b,c;
int f[5003][5003];
inline int qr(){
char ch; //int sign=1;
while((ch=getchar())<'0'||ch>'9');
// if(ch=='-')sign=-1;
int res=ch^48;
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch^48);
return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr(),m=qr();
for(rg i=1;i<=n;++i){
a=qr()+1,b=qr()+1,c=qr();
f[a][b]=c;
}
for(rg i=1;i<=5001;++i)
for(rg j=1;j<=5001;++j)
f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
for(rg i=m;i<=5001;++i){
for(rg j=m;j<=5001;++j){
ans=max(ans,f[i][j]-f[i-m][j]-f[i][j-m]+f[i-m][j-m]);
}
}printf("%d\n",ans);
return 0;
}
$ POJ~3263~Tallest~Cow $（前缀和，贪心）
$ solotion: $
很久以前就做过，一道比较有意思的前缀和做法我们首先可以贪心想到牛的身高每次只减1，然后求出最少的减少次数每头牛的身高减少次数是确定的，我们对于每一对可以互相看见的牛，他们中间的牛的身高都要减少一次所以我们在 $ A_i $ 处加一，在 $ B_i+1 $ 处减一然后求前缀和就可以知道每一头牛的减少次数然后这题不用担心每头牛都要比两端点的牛矮，所有区间一定是包含关系，而不会相交
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
int n,m,h,q,a,b;
int s[10001];
bool use[10001][10001];
inline int qr(){
char ch;
while((ch=getchar())<'0'||ch>'9');
int res=ch^48;
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch^48);
return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr(),m=qr(),h=qr(),q=qr();
while(q--){
a=qr(),b=qr();
if(a>b)swap(a,b);
if(use[a][b])
continue;
use[a][b]=1;
--s[a+1];
++s[b];
}
for(rg i=1;i<=n;++i){
s[i]=s[i]+s[i-1];
printf("%d\n",h+s[i]);
}
return 0;
}
$ POJ~1845~Sumdiv $（约数和定理）（分治）
题目大意：
求 $ A^B $ 的所有约数之和
$ solotion: $
首先要知道约数和定理： $ (1+p_1+p_1^2+...+p_1^{c_1})(1+p_2+p_2^2+...+p_2^{c_2})...*(1+p_k+p_k^2+...+p_k^{c_k}) $然后本题就比较好做了， $ A^B $ 的所有约数之和就是让上式中所有 $ c_i $ 乘上 $ B $ 即可然后括号里面的东西直接用分治求即可
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
const int mod=9901;
int n,m,ans;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline int ksm(ll x,int y){
ll res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod; y>>=1;
}return res;
}
inline int ask(int x,int y){
if(y==1)return x;
if(y&1) return ((ll)ask(x,y>>1)*(ksm(x,y>>1)+1)%mod+ksm(x,y)%mod)%mod;
else return (ll)ask(x,y>>1)*(ksm(x,y>>1)+1)%mod;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while(~scanf("%d%d",&n,&m)){
if(m==0){puts("1");continue;}
ans=1;
for(rg i=2;i*i<=n;++i){
if(n%i)continue;
rg x=0; while(!(n%i))++x,n/=i;
ans=(ll)ans*(ask(i%mod,x*m)+1)%mod;
}if(n!=1)ans=(ll)ans*(ask(n%mod,m)+1)%mod;
printf("%d\n",ans);
}
return 0;
}
$ POJ~2018~Best~Cow~Fences $（二分答案构造新权值）
单独的一篇题解
$ POJ~3889~Fractal~Streets $（模拟）
单独的一篇题解
$ Codeforces~670C~Cinema $（离散化）
$ solotion: $
很傻的一道题目，直接离散化求出每种语言对应的人然后枚举电影，求出其权值，最大的那个就是答案
$ code: $
#include<stdio.h>
#include<map>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int m,ple=0,sat=0,fi=1,sci[200005],bn[200005],cn;
map<int,int> mp;
for(int i=0;i<n;i++)
{
scanf("%d",&sci[i]);
mp[sci[i]]++;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&bn[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&cn);
if(mp[bn[i]]>ple)
{
ple=mp[bn[i]];
sat=mp[cn];
fi=i;
}
else if(mp[bn[i]]==ple&&mp[cn]>sat)
{
sat=mp[cn];
fi=i;
}
}
printf("%d\n",fi);
}
return 0;
}
题目大意：
依次读入数列，求每一个数加入时的中位数。
$ solotion: $
直接用小根堆加大根堆维护一下就行每次记录两边总数，判断加到哪边即可
$ code: $
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
int n,t,x,a,b,cnt;
inline void read(int &x){
char ch=getchar();
char c=ch;
x=0;
while(ch<'0' || ch>'9') {
c=ch;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
if(c== '-') x=-x;
}
std::priority_queue <int> lq,sq;
int main(){
read(t);
while(t--){
read(cnt);
read(n);
while(!lq.empty()) lq.pop();
while(!sq.empty()) sq.pop();
cout<<cnt<<' '<<((n+1)/2)<<endl;
for(int i = 1;i <= n;++ i){
read(x);
lq.push(x);
sq.push(-x);
if(i%2==0) continue;
while(lq.top()!=-sq.top()){
a=lq.top();
lq.pop();
b=-sq.top();
sq.pop();
sq.push(-a);
lq.push(b);
}
cout<<lq.top()<<' ';
if(((i+1)/2)==0) puts("");
else if((n%2==1 && i==n) || (n%2==0 && i==n-1)) puts("");
}
}
return 0;
}
$ POJ~2299~Ultra-QuickSort $（逆序对）
题目大意：
求一个序列里的逆序对。
$ solotion: $
没想会在基本算法里碰见这个，挺怀念的。我们用树状数组维护一下（需要离散化），和最长上升子序列里一个板子
$ POJ~3614~Sunscreen $（贪心，优先队列）
$ solotion: $
这个题目比较容易想到贪心我们将奶牛和防晒霜分开，都以阳光强度（最小值）排序然后我们可以想到枚举防晒霜用一个优先队列依次存下当前防晒霜能保护的牛然后我们用优先队列求出右端点（最大阳光强度）最小的牛用这个防晒霜这样肯定比用最大阳光强度的好，因为我们将最大阳光强度大的留给了后面的防晒霜。而最小阳光强度在枚举时得到了保障（我们是依次加入防晒霜能保护的牛的）。
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,ans;
struct su{
int x,y;
inline bool operator <(const su &z)const{
return x<z.x;
}
}a[2505],b[2505];
struct pi{
int x,y;
inline bool operator <(const pi &z)const{
return y>z.y;
}
};
priority_queue<pi> q;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr(); m=qr();
for(rg i=1;i<=n;++i)
a[i].x=qr(),a[i].y=qr();
sort(a+1,a+n+1);
for(rg i=1;i<=m;++i)
b[i].x=qr(),b[i].y=qr();
sort(b+1,b+m+1);
for(rg i=1,l=1;i<=m;++i){
while(l<=n&&a[l].x<=b[i].x){
pi x; x.x=l; x.y=a[l].y; q.push(x); ++l;
}
while(!q.empty()&&q.top().y<b[i].x)q.pop();
while(!q.empty()&&b[i].y){
++ans; --b[i].y; q.pop();
}
}printf("%d\n",ans);
return 0;
}
$ POJ~3190~Stall~Reservation $（前缀和，优先队列）
$ solotion: $
这道题的最小畜栏数是确定的我们直接用差分约束前缀和的方法即可得出答案但是这道还需要我们输出畜栏序号，这就需要我们动态维护那几个畜栏没有用过我们用优先队列优化，按左端点枚举每一头牛，然后用优先队列记录它的右端点以及它用的哪一个畜栏，（畜栏的使用状态也需要用一个优先队列维护（因为我们要最小化畜栏数目））然后在枚举过程中还要对优先队列进行取出操作，将用完的畜栏记录下来，病房会优先队列里去
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,tt,ans;
int as[50005];
struct su{
int l,r,id;
inline bool operator <(const su &x)const{
return l<x.l;
}
}a[50005];
struct pi{
int x,y;
inline bool operator <(const pi &z)const{
return x>z.x;
}
};
priority_queue<pi> q;
priority_queue<int, vector<int>, greater<int> >p;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=qr();
for(rg i=1;i<=n;++i)
a[i].l=qr(),a[i].r=qr(),a[i].id=i,p.push(i);
sort(a+1,a+n+1);
for(rg i=1;i<=n;++i){
while(!q.empty()&&q.top().x<a[i].l){
p.push(q.top().y); q.pop();
}as[a[i].id]=p.top(); p.pop();
pi x; x.x=a[i].r; x.y=as[a[i].id]; q.push(x);
ans=max(ans,as[a[i].id]);
}
printf("%d\n",ans);
for(rg i=1;i<=n;++i)
printf("%d\n",as[i]);
return 0;
}
$ POJ~1328~Radar~Installation $ （贪心，单调队列）
$ Solution: $
很早之前就做过了，好像之前叫稻草人来着就是算出每一个点在x轴上可以允许的最左端和最右端然后按最左然后按最左端排序，挨个在优先队列里加入最右端信息一旦到达一个最右端，将它覆盖的所有点删去（包括优先队列的某些信息也会失效，用一个bool数组记录每个是否已被覆盖即可）
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int t,n,d,ans;
struct su{
db x,y,l,r;
inline void find(){
db k=sqrt((db)d*d-y*y);
l=x-k; r=x+k;
}
inline bool operator <(su z){
return l<z.l;
}
}a[1005];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while(++t){ ans=0;
n=qr(); d=qr();
if(!n&&!d)break;
for(rg i=1;i<=n;++i){
a[i].x=qr(); a[i].y=qr();
a[i].find(); if(a[i].y>d)ans=-1;
} sort(a+1,a+n+1);
if(ans!=-1){ db s=-1e9;
for(rg i=1;i<=n;++i){
//cout<<a[i].l<<" "<<a[i].r<<endl;
if(a[i].l<=s)
s=min(a[i].r,s);
else ++ans, s=a[i].r;
}
} printf("Case %d: %d\n",t,ans);
}
return 0;
}
$ POJ~2054~Color~a~Tree $ （复杂的贪心）
单独的一篇题解
$ POJ~2965~The~Pilots~Brother'~Refrigerator $ （状态压缩，结论）
$ Solution: $
数据范围很小，可以直接状态压缩，然后暴力枚举但是这一题还有一个结论可以更快：对于一个处于闭合的开关将它所在行列上每一个元素异或1（初始为0）最后还为1的格子需要改变状态。这个结论博主也不知道怎么证，所以还是第一种方案保险
$ Code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int a,b,n,ans;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
char ch; a=15; b=4369;
for(rg i=1;i<=4;++i,a<<=4,b=4369){
for(rg j=1;j<=4;++j,b<<=1){
while((ch=getchar())!='+'&&ch!='-')continue;
if(ch=='+') n^=a,n^=b,n^=a&b;
}
} rg x=n;
while(x)ans+=(x&1),x>>=1;
printf("%d\n",ans);
for(rg i=1;i<=4;++i)
for(rg j=1;j<=4;++j,n>>=1)
if(n&1)printf("%d %d\n",i,j);
return 0;
}
$ POJ~2083~Fractal $ （模拟）
$ Solution: $
最近总是碰到这种模拟题，直接 $ bitset $ 模拟就行了。置于转移，我们直接用二进制的或运算和左右移模拟复制粘贴就好然后判断输出
$ Code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<bitset>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int t,f,n,m=1;
bitset<805> s[805];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
s[1][1]=1; n=7;
for(rg i=2;i<=n;++i,m*=3){ //扩大
for(rg j=m+1;j<=m*2;++j)
s[j]=s[j-m]<<m;//中间的那一部分
for(rg j=1;j<=m;++j){
s[j]|=s[j]<<(m*2);//右上那部分
s[j+m*2]=s[j]; //第三行复制第一行即可
}
}
while((n=qr())!=-1){
rg x=1;
for(rg i=1;i<n;++i)x*=3;
for(rg i=1;i<=x;++i){
for(rg j=1;j<=x;++j){
if(s[i][j])putchar(88);
else putchar(32);
}puts("");//快速输出
}puts("-");
}
return 0;
}
$ POJ~3741~Raid $ （平面最近点对）
单独的一篇题解
$ CH~0805~ $ 防线 (二分，前缀和，特殊性质)
单独的一篇题解
$ POJ~3197~Corral~the~Cows $ （二分，最大子矩阵）
单独的一篇题解
$ BZOJ~1045~ $ 糖果传递 （中位数，环形均分纸牌）
$ Solution: $
对于一个环形，我们总要去想有没有断环的方法而这道题目有一个性质：最优答案一定可以存在两个相邻的人之间没有联系，相当于一条链于是我们用前缀和来计算每个人需要操作的次数： $ f[i]=|s[i]-s[k]| $ ， $ s[k] $ 为 链的左端我们发现只要 $ s[k] $ 为 $ s[i] $ 的中位数时，总和最小，于是我们找到最小的那个中位数计算答案。
$ Code: $
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
ll n,a[N],sum,s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
sum/=n;
for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i];
sort(s+1,s+n+1);
sum=0;
for(int i=1;i<=n;i++)sum+=abs(s[n/2+1]-s[i]);
cout<<sum;
return 0;
}
$ POJ~1723~Soldiers $ (中位数)
单独的一篇题解
$ POJ~1220~Number~Base~Conversion $ （进制转换）
$ Solution: $
这个就是高精度的进制转换，我们模拟一下就好
$ Code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int t,a,b,n,tt;
int s[100005];
int as[100005];
string c;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
t=qr();
while(t--){ tt=0;
a=qr(); b=qr();
cin>>c; n=c.size();
for(rg i=0;i<n;++i){
if(c[i]>='0'&&c[i]<='9')
s[i+1]=c[i]-'0';
if(c[i]>='A'&&c[i]<='Z')
s[i+1]=c[i]-'A'+10;
if(c[i]>='a'&&c[i]<='z')
s[i+1]=c[i]-'a'+36;
} rg f=n,k=0;
while(f){
k=0; f=0;
for(rg i=f;i<=n;++i){
k=s[i]+k*a;
s[i]=k/b;
k%=b;
if(!f&&s[i])f=i;
}as[++tt]=k;
}
cout<<a<<" "<<c<<endl<<b<<" ";
for(rg i=tt;i>=1;--i){
if(as[i]>=0&&as[i]<=9)
putchar(as[i]+'0');
if(as[i]>=10&&as[i]<=35)
putchar(as[i]+'A'-10);
if(as[i]>=36&&as[i]<=61)
putchar(as[i]+'a'-36);
}puts(""); puts("");
}
return 0;
}
$ POJ~1050~To~the~Max $ （最大子矩阵和）
单独的一篇题解
$ HDOJ~4864~Task $ （贪心）
$ Solution: $
很套路的一道贪心首先我们的价值算法和复杂度挖了一个坑：最小的时间价值比最大的难度价值要高所以我们贪心可以直接按时间来，所以我们先按难度排序然后用优先队列维护每一个机器能完成的最长时间的任务然后暴力算答案即可（我们可以发现难度一维并不会产生后效性）
$ Code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
ll ans;
int n,m,t;
struct su{
int x,y;
inline bool operator <(const su &z)const{
if(x==z.x)return y>z.y;
return x>z.x;
}
}a[100005],b[100005];
multiset<su> s,k;
inline bool cmp(const su &x,const su &y){
return x.y<y.y;
}
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while(~scanf("%d%d",&n,&m)){
t=0; ans=0; s=k;
for(rg i=1;i<=n;++i)
a[i].x=qr(),a[i].y=qr();
for(rg i=1;i<=m;++i)
b[i].x=qr(),b[i].y=qr();
sort(a+1,a+n+1,cmp);
sort(b+1,b+m+1,cmp);
for(rg i=1,j=1;i<=n;++i){
while(j<=m&&b[j].y<=a[i].y)
s.insert(b[j]), ++j;
multiset<su>::iterator it;
it=s.lower_bound(a[i]);
if(it==s.end())continue;
ans+=500*((*it).x)+2*((*it).y);
s.erase(it); ++t;
}printf("%d %lld\n",t,ans);
}
return 0;
}
转载于:https://www.cnblogs.com/812-xiao-wen/p/11249256.html
