目录
显示
一份咕咕了两个月的题解?(其实有两道题的题解都在洛谷上发布了)
A. Convention
题目链接
https://www.luogu.org/problem/P5119
题解
本题可以采用二分答案的方法解决。
先将牛到达的时间排序,然后二分最长等待时间即可。
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
//freopen("convention.in","r",stdin);
//freopen("convention.out","w",stdout);
int n,m,c;
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1];
while(l<r)
{
int mid=(l+r)>>1,cnt=1,sta=1;
for(int i=1;i<=n;i++)
if(a[i]-a[sta]>mid||i-sta+1>c)
//如果等待时间超过了二分中点mid或当前车辆已经满载,就重新发一辆车
{
cnt++;
sta=i;
}
if(cnt<=m)r=mid;//该时间下车辆数充足,等待时间可以更小
else l=mid+1;//车辆不足,等待时间要更长
}
printf("%d\n",l);
fclose(stdin);
fclose(stdout);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
//freopen("convention.in","r",stdin);
//freopen("convention.out","w",stdout);
int n,m,c;
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1];
while(l<r)
{
int mid=(l+r)>>1,cnt=1,sta=1;
for(int i=1;i<=n;i++)
if(a[i]-a[sta]>mid||i-sta+1>c)
//如果等待时间超过了二分中点mid或当前车辆已经满载,就重新发一辆车
{
cnt++;
sta=i;
}
if(cnt<=m)r=mid;//该时间下车辆数充足,等待时间可以更小
else l=mid+1;//车辆不足,等待时间要更长
}
printf("%d\n",l);
fclose(stdin);
fclose(stdout);
return 0;
}
#include <cstdio> #include <algorithm> using namespace std; int a[100005]; int main() { //freopen("convention.in","r",stdin); //freopen("convention.out","w",stdout); int n,m,c; scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=0,r=a[n]-a[1]; while(l<r) { int mid=(l+r)>>1,cnt=1,sta=1; for(int i=1;i<=n;i++) if(a[i]-a[sta]>mid||i-sta+1>c) //如果等待时间超过了二分中点mid或当前车辆已经满载,就重新发一辆车 { cnt++; sta=i; } if(cnt<=m)r=mid;//该时间下车辆数充足,等待时间可以更小 else l=mid+1;//车辆不足,等待时间要更长 } printf("%d\n",l); fclose(stdin); fclose(stdout); return 0; }
B. Convention II
题目链接
https://www.luogu.org/problem/P5120
题解
一道很暴力的模拟题。
采用优先队列维护等待序列,每次让等待队列的堆顶出队,并计算答案。
(代码量还不小)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node
{
long long id,a,t;
bool operator<(const node&a)const
{
return a.id<id;
}
}a[100005];
struct lian
{
long long t;
vector<int> l;
}b[100005];
priority_queue<node> q;
map<int,int> ma;
bool cmp(const node&a,const node&b)
{
return a.a<b.a||(a.a==b.a&&a.id<b.id);
}
int main()
{
long long n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].t;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
long long x=a[1].a,cnt=1;
b[1].t=x;
ma[1]=x;
for(int i=1;i<=n;i++)
if(a[i].a==x)b[cnt].l.push_back(i);
else
{
b[++cnt].t=a[i].a;
ma[cnt]=a[i].a;
b[cnt].l.push_back(i);
}
long long curt=a[1].a,curl=b[1].t,inque=0,pi=1;
for(vector<int>::iterator it=b[1].l.begin();it!=b[1].l.end();it++)
q.push(a[*it]),inque++;
while(!q.empty())
{
node eatc=q.top();//队首奶牛出队并计算答案
ans=max(ans,curt-eatc.a);
curt+=eatc.t;
q.pop();
while(ma[pi+1]<=curt&&ma[pi+1]!=0)//到达的奶牛都入队等待
{
for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
q.push(a[*it]),inque++;
curl=ma[pi];
if(curl==0)break;
}
if(q.empty()&&inque<n)
{
for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
q.push(a[*it]),inque++;
curl=ma[pi];
curt=max(a[inque].a,curt);
}
}
cout<<ans<<endl;
return 0;
}
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node
{
long long id,a,t;
bool operator<(const node&a)const
{
return a.id<id;
}
}a[100005];
struct lian
{
long long t;
vector<int> l;
}b[100005];
priority_queue<node> q;
map<int,int> ma;
bool cmp(const node&a,const node&b)
{
return a.a<b.a||(a.a==b.a&&a.id<b.id);
}
int main()
{
long long n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].t;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
long long x=a[1].a,cnt=1;
b[1].t=x;
ma[1]=x;
for(int i=1;i<=n;i++)
if(a[i].a==x)b[cnt].l.push_back(i);
else
{
b[++cnt].t=a[i].a;
ma[cnt]=a[i].a;
b[cnt].l.push_back(i);
}
long long curt=a[1].a,curl=b[1].t,inque=0,pi=1;
for(vector<int>::iterator it=b[1].l.begin();it!=b[1].l.end();it++)
q.push(a[*it]),inque++;
while(!q.empty())
{
node eatc=q.top();//队首奶牛出队并计算答案
ans=max(ans,curt-eatc.a);
curt+=eatc.t;
q.pop();
while(ma[pi+1]<=curt&&ma[pi+1]!=0)//到达的奶牛都入队等待
{
for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
q.push(a[*it]),inque++;
curl=ma[pi];
if(curl==0)break;
}
if(q.empty()&&inque<n)
{
for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
q.push(a[*it]),inque++;
curl=ma[pi];
curt=max(a[inque].a,curt);
}
}
cout<<ans<<endl;
return 0;
}
#include <cstdio> #include <iostream> #include <algorithm> #include <iterator> #include <vector> #include <queue> #include <map> using namespace std; struct node { long long id,a,t; bool operator<(const node&a)const { return a.id<id; } }a[100005]; struct lian { long long t; vector<int> l; }b[100005]; priority_queue<node> q; map<int,int> ma; bool cmp(const node&a,const node&b) { return a.a<b.a||(a.a==b.a&&a.id<b.id); } int main() { long long n,ans=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].a>>a[i].t; a[i].id=i; } sort(a+1,a+n+1,cmp); long long x=a[1].a,cnt=1; b[1].t=x; ma[1]=x; for(int i=1;i<=n;i++) if(a[i].a==x)b[cnt].l.push_back(i); else { b[++cnt].t=a[i].a; ma[cnt]=a[i].a; b[cnt].l.push_back(i); } long long curt=a[1].a,curl=b[1].t,inque=0,pi=1; for(vector<int>::iterator it=b[1].l.begin();it!=b[1].l.end();it++) q.push(a[*it]),inque++; while(!q.empty()) { node eatc=q.top();//队首奶牛出队并计算答案 ans=max(ans,curt-eatc.a); curt+=eatc.t; q.pop(); while(ma[pi+1]<=curt&&ma[pi+1]!=0)//到达的奶牛都入队等待 { for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++) q.push(a[*it]),inque++; curl=ma[pi]; if(curl==0)break; } if(q.empty()&&inque<n) { for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++) q.push(a[*it]),inque++; curl=ma[pi]; curt=max(a[inque].a,curt); } } cout<<ans<<endl; return 0; }
C. Mooyo Mooyo
题目链接
https://www.luogu.org/problem/P5121
题解
怎么还是模拟…
本题是一个简单模拟题。
每次按题意 dfs 找出连通块,并将其删除即可。
注意当一个格子下面为空的时候,不要忘了把它往下移动。
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
struct node
{
int x,y;
bool operator<(const node&a)const
{
return x<a.x||(x==a.x&&y<a.y);
}
};
set<node> se;
char s[105][15];
int vis[105][15],n,k;
int dfs(int x,int y,char cur)//找连通块
{
vis[x][y]=1;
se.insert({x,y});//将找到的格子加入集合,便于后面执行删除操作
int ans=1;
if((!vis[x-1][y])&&s[x-1][y]==cur)ans+=dfs(x-1,y,cur);
if((!vis[x+1][y])&&s[x+1][y]==cur)ans+=dfs(x+1,y,cur);
if((!vis[x][y-1])&&s[x][y-1]==cur)ans+=dfs(x,y-1,cur);
if((!vis[x][y+1])&&s[x][y+1]==cur)ans+=dfs(x,y+1,cur);
return ans;
}
int main()
{
//freopen("mooyomooyo.in","r",stdin);
//freopen("mooyomooyo.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
while(1)
{
memset(vis,0,sizeof(vis));
bool flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=10;j++)
if((!vis[i][j])&&s[i][j]!='0')
{
int cnt=dfs(i,j,s[i][j]);
if(cnt>=k)
{
for(set<node>::iterator it=se.begin();it!=se.end();it++)
s[(*it).x][(*it).y]='0';
flag=true;
}
se.clear();
}
for(int i=n-1;i>=1;i--)//模拟下落过程
for(int j=1;j<=10;j++)
{
if(s[i][j]=='0')continue;
int x=i,y=j;
while(s[x+1][y]=='0')
swap(s[x][y],s[x+1][y]),x++;
}
if(!flag)break;
}
for(int i=1;i<=n;i++)
puts(s[i]+1);
return 0;
}
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
struct node
{
int x,y;
bool operator<(const node&a)const
{
return x<a.x||(x==a.x&&y<a.y);
}
};
set<node> se;
char s[105][15];
int vis[105][15],n,k;
int dfs(int x,int y,char cur)//找连通块
{
vis[x][y]=1;
se.insert({x,y});//将找到的格子加入集合,便于后面执行删除操作
int ans=1;
if((!vis[x-1][y])&&s[x-1][y]==cur)ans+=dfs(x-1,y,cur);
if((!vis[x+1][y])&&s[x+1][y]==cur)ans+=dfs(x+1,y,cur);
if((!vis[x][y-1])&&s[x][y-1]==cur)ans+=dfs(x,y-1,cur);
if((!vis[x][y+1])&&s[x][y+1]==cur)ans+=dfs(x,y+1,cur);
return ans;
}
int main()
{
//freopen("mooyomooyo.in","r",stdin);
//freopen("mooyomooyo.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
while(1)
{
memset(vis,0,sizeof(vis));
bool flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=10;j++)
if((!vis[i][j])&&s[i][j]!='0')
{
int cnt=dfs(i,j,s[i][j]);
if(cnt>=k)
{
for(set<node>::iterator it=se.begin();it!=se.end();it++)
s[(*it).x][(*it).y]='0';
flag=true;
}
se.clear();
}
for(int i=n-1;i>=1;i--)//模拟下落过程
for(int j=1;j<=10;j++)
{
if(s[i][j]=='0')continue;
int x=i,y=j;
while(s[x+1][y]=='0')
swap(s[x][y],s[x+1][y]),x++;
}
if(!flag)break;
}
for(int i=1;i<=n;i++)
puts(s[i]+1);
return 0;
}
#include <cstdio> #include <cstring> #include <set> using namespace std; struct node { int x,y; bool operator<(const node&a)const { return x<a.x||(x==a.x&&y<a.y); } }; set<node> se; char s[105][15]; int vis[105][15],n,k; int dfs(int x,int y,char cur)//找连通块 { vis[x][y]=1; se.insert({x,y});//将找到的格子加入集合,便于后面执行删除操作 int ans=1; if((!vis[x-1][y])&&s[x-1][y]==cur)ans+=dfs(x-1,y,cur); if((!vis[x+1][y])&&s[x+1][y]==cur)ans+=dfs(x+1,y,cur); if((!vis[x][y-1])&&s[x][y-1]==cur)ans+=dfs(x,y-1,cur); if((!vis[x][y+1])&&s[x][y+1]==cur)ans+=dfs(x,y+1,cur); return ans; } int main() { //freopen("mooyomooyo.in","r",stdin); //freopen("mooyomooyo.out","w",stdout); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); while(1) { memset(vis,0,sizeof(vis)); bool flag=false; for(int i=1;i<=n;i++) for(int j=1;j<=10;j++) if((!vis[i][j])&&s[i][j]!='0') { int cnt=dfs(i,j,s[i][j]); if(cnt>=k) { for(set<node>::iterator it=se.begin();it!=se.end();it++) s[(*it).x][(*it).y]='0'; flag=true; } se.clear(); } for(int i=n-1;i>=1;i--)//模拟下落过程 for(int j=1;j<=10;j++) { if(s[i][j]=='0')continue; int x=i,y=j; while(s[x+1][y]=='0') swap(s[x][y],s[x+1][y]),x++; } if(!flag)break; } for(int i=1;i<=n;i++) puts(s[i]+1); return 0; }