本文共 2169 字，大约阅读时间需要 7 分钟。
题意：
给你n个地点的位置，他们是从小到大的顺序，然后每个位置都会有m个飞船，每个飞船能够传送一定的距离，如果使用该飞船会消耗掉一定的IQ，问如果一个人从1号位置开始选择飞船到达n号位置，最少的IQ花费是多少？
思路：
对于i位置与i+1位置，我们只要找出m个飞船中传送距离ds大于x[i + 1] - x[i]的花费IQ最少的即可。可是如何维护大于x[i + 1] - x[i]这个区间的里面最小的IQ消耗呢？ 首先将相邻两点的距离求出来，然后从大到小排序，然后将m个飞船的创送距离从大到小排序，然后每次枚举到相邻两点之间的距离时，然后检查没有放入优先队列的可能比当前点的距离大的飞船，然后放进去，这样就能保证维护大于该距离的飞船的最IQ了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("data.in", "r", stdin)#define Write() freopen("d.out", "w", stdout)#define M 100007#define N 10004using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;struct node{ ll ds; ll iq; bool operator < (const node &a) const { return iq > a.iq; }}nd[M],tmp;ll dis[N],x[N];int n,m;priority_queue pQ;int cmp(node a,node b){ if (a.ds != b.ds) return a.ds > b.ds; else return a.iq < b.iq;}int cmpx(int a,int b) { return a > b; }int main(){// Read(); int T,i,j; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); while (!pQ.empty()) pQ.pop(); for (i = 1; i <= n; ++i) scanf("%lld",&x[i]); for (i = 1; i < n; ++i) dis[i] = x[i + 1] - x[i]; sort(dis + 1,dis + n,cmpx); for (i = 1; i <= m; ++i) scanf("%lld%lld",&nd[i].ds,&nd[i].iq); sort(nd + 1,nd + 1 + m,cmp); ll ans = 0; int left = 1; bool flag = false; for (i = 1; i < n; ++i) { ll dc = dis[i]; for (j = left; j <= m; ++j) { left = j; if (nd[j].ds < dc) break; pQ.push(nd[j]); } if (pQ.empty()) { flag = true; break; } ans += pQ.top().iq; } if (flag) printf("Impossible\n"); else printf("%lld\n",ans); } return 0;}
转载于:https://www.cnblogs.com/E-star/archive/2013/06/02/3114164.html
