admin管理员组文章数量:1577816
ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2018–12–09
C.Emergency Evacuation(贪心)
原题:
题意:把指定的人从同一出口送出车外,且同一位置不能同时有两个人,求所需的最短时间。
当时第一眼感觉是贪心,但是从把所有人都推出的角度考虑感觉不好找到贪心策略,模拟又不现实,肯定会炸。。。
解题方法:
逆向思维,考虑将所有人从出口处送回原位置,并且依据各自原位置到出口的距离进行排序,将距离较远的排在前面,可以理解为原位置离出口较远的人先进入,而原位置离出口较近的人后进入,这样可以让花费的时间达到最小,从而得到最优解。
#include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define scan(n) scanf("%d",&n)
struct per
{
int r,c;//原位置
int d;//原位置离出口的距离
};
struct per pe[500005];
bool cmp(struct per a,struct per b)
{
return a.d>b.d;
}
int main()
{
int r,s,p,i;
cin>>r>>s>>p;
for(i=0;i<p;i++)
{
cin>>pe[i].r>>pe[i].c;
if(pe[i].c>s)
pe[i].d=(pe[i].c-s)+(r-pe[i].r+1);
else
pe[i].d=(s-pe[i].c+1)+(r-pe[i].r+1);
}
sort(pe,pe+p,cmp);
int k=1;//在队列中等待进入车厢的时间
int maxtime=pe[0].d;
for(i=1;i<p;i++)
{
if(pe[i].d+k>maxtime)
maxtime=pe[i].d+k;
k++;
}
cout<<maxtime<<endl;
return 0;
}
本文标签: 贪心EmergencyEvacuation
版权声明:本文标题:C.Emergency Evacuation(贪心) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1727824031a1132056.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论