迷你滨

用户名：uq_20629230267

访问量：9282

签　名：

等　　级
排　　名	2135
经　　验	2437
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)
浏览：1425

你可能喜欢

A+B for Input-Output Practice (IV) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯2023年第十四届省赛真题-小蓝的旅行计划(优先队列+线段树or树状数组)

　　作者: 迷你滨　　　　发表时间：2023-04-28 16:15:14 浏览：1135　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-小蓝的旅行计划

### 蓝桥杯2023年第十四届省赛真题-小蓝的旅行计划(优先队列+线段树or树状数组)
***
若没有油箱的限制，仅用优先队列即可。将所有加油站扔到堆里，贪心得在油价最少的加油站加油。

但若有限制，在一个加油站加油后，之后到达的加油站的到达油量也要更新，能加的油量也要更新，故采用线段树or树状数组维护区间到达加油站的油量的最大值。即，若要到达加油站$$i$$，选择在之前的加油站$$j$$加油，能加的油量为：$$min(lim[j],maxVolumn-rest[j,i-1])$$.
其中，$$lim[j]$$表示加油站 $$j$$ 的加油限制，$$maxVolumn$$为油箱容量，$$rest[j,i-1]$$表示在加油站$$j$$到加油站$$i-1$$中各到达油量的最大值，保证加油后油量不超过最大油量。

复杂度$$O(n\*log(n))$$，常数较大。
```java
import java.io.*;
import java.util.*;
  
public class Main{
    static int maxn = 200005,n,m,inf=(int)1e9;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    
    static class gas implements Comparable<gas>{
		long c;
		int id;
		public gas(int i,long a) {
			c=a;id=i;
		}
		@Override
		public int compareTo(gas o) {
			// TODO Auto-generated method stub
			return this.c -o.c>0?1:-1;
		}
		
	}
    
    static int rest[] = new int [maxn<<2];
    static int k[] = new int [maxn<<2];
    static int dis[] = new int [maxn];
	static int lim[] = new int [maxn];
	static int cost[] = new int [maxn];
    static int vol = 0;
    
    static void build(int i,int l,int r) {
    	if(l == r) {
    		rest[i]=0; //到达时油量
    		return ;
    	}
    	int mid = (l+r)/2;
    	build(i<<1,l,mid);build(i<<1|1,mid+1,r);
    	up(i);
    }
    
    static void up(int i) {
    	rest[i] = Math.max(rest[i<<1],rest[i<<1|1]);
    }
    
    static void pd(int i) {
    	if(k[i]!=0) {
    		k[i<<1] += k[i]; k[i<<1|1] += k[i];
    		rest[i<<1] += k[i]; rest[i<<1|1] +=k[i];
    		k[i] = 0;
    	}
    }
    
    static int query(int i,int l,int r,int ll,int rr) {
    	if(ll<=l && r <=rr) return rest[i];
    	pd(i);
    	int res = 0;
    	int mid = (l+r)/2;
    	if(mid >= ll) res = Math.max(res,query(i<<1,l,mid,ll,rr));
    	if(mid < rr) res = Math.max(res,query(i<<1|1,mid+1,r,ll,rr));
    	up(i);
    	return res;
    }
	
    static void add(int i,int l,int r,int ll,int rr,int v) {
    	if(ll<=l && r <=rr) {
    		rest[i]+=v;k[i]+=v;
    		return;
    	}
    	pd(i);
    	int mid = (l+r)/2;
    	if(mid >= ll) add(i<<1,l,mid,ll,rr,v);
    	if(mid < rr) add(i<<1|1,mid+1,r,ll,rr,v);
    	up(i);
    }
    
	static void solve() throws IOException{
		n = I();m = I();
		vol = m;
		PriorityQueue<gas> q = new PriorityQueue<>();
		for(int i=1;i<=n;i++) {
			dis[i]=I();cost[i]=I();lim[i]=I();
		}
		build(1,1,n);
		for(int i=1;i<=n;i++) {
			vol -= dis[i];
			while(vol<0) {
				if(q.isEmpty()) {
					pw.println(-1);return;
				}
				gas a = q.poll();
				int cnt = Math.min(m-query(1,1,n,a.id,i-1), lim[a.id]);
				if(cnt<=0) continue;
				if(cnt <= -vol) {
					ans += a.c *cnt;
					vol += cnt;
					lim[a.id] = 0;
					add(1,1,n,a.id,i-1,cnt);
				}
				else {
					ans += a.c *(-vol);
					lim[a.id] = cnt + vol;
					add(1,1,n,a.id,i-1,-vol);
					q.add(new gas(a.id,a.c));
					vol=0;
				}
			}
			if(vol>0) add(1,1,n,i,i,vol);
			lim[i] = Math.min(lim[i], m-vol);
			q.add(new gas(i,cost[i]));
		}
		pw.println(ans);
	}
}

```

0.0分

14 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

迷你滨

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

A+B for Input-Output Practice (IV) （C语言代码）

采药（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯2023年第十四届省赛真题-小蓝的旅行计划(优先队列+线段树or树状数组)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

字符逆序（C语言代码）

printf基础练习2 （C语言代码）

Tom数（C语言代码）

永远的丰碑（C语言代码）

格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

迷你滨

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

A+B for Input-Output Practice (IV) （C语言代码）

采药 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯2023年第十四届省赛真题-小蓝的旅行计划(优先队列+线段树or树状数组)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

字符逆序 （C语言代码）

printf基础练习2 （C语言代码）

Tom数 （C语言代码）

永远的丰碑 （C语言代码）

格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

采药（C++代码）

　　评论区

字符逆序（C语言代码）

Tom数（C语言代码）

永远的丰碑（C语言代码）

格式化数据输出（C语言代码）