D2晚上
2024-10-06 20:24:17
发布于:浙江
// 7 8 9 3+4=9
// 1 2 3 4 5 6 7 8 9 10
// 通过dfs暴力的方式求解所有的买票方案。
// 当张三在某一天的时候d_i天的时候:
// 1.购买d_i天的票
// 2.购买d_1+i到di+1天的票,【di,di+1】,包含di和di+1的两天票
// 3.购买d_2+i到di+1天的票,【d1,di+2】,包含三天的票
// 对于不同的选择不知道哪一种是最优的,所以需要for循环枚举
// 当张三将di天的及以前的票全部买完,需要考虑di+1天
// 当所有的处理完毕,则知道哪一种方案,花费最小
// #include<bits/stdc++.h>
// long long n,k;//天数 手续费
// long long d[1000202];//d1到dn的情况
// long long ans;//最终答案
// using namespace std;
// void dfs(int st,long long now){//当前处理到st天的时候,当前的花费为now
// if(st==n+1){//st表示前n天都处理完了
// ans=min(ans,now);
// return ;
// }
// for(int i=st;i<=n;i++){//当前这一次的票买到那一天 i表示d_st到d_i的票
// dfs(i+1,now+(d[i]-d[st]+1)+k);
// //i+1表示下一次买di+1 天的
// //now带入为当前这一次的花费
// }
// }
// int main(){
// freopen("perform.in","r",stdin);
// freopen("perform.out","w",stdout);
// cin>>n>>k;
// for(int i=1;i<=n;i++)cin>>d[i];
// ans=n*(1+k);//假设每一次都是只买一天的票,一共花费n天,总花费n*(1+d)
// dfs(1,0);
// cout<<ans<<endl;+1+k钱
// fclose(stdin),;
// fclose(stdout);
// return 0;
// }
// 1.(di)天的票,花费1+k元,如果买的是【di,di+1】天的票(di+1-di)+1+k钱,只需要在原基础上多花d[i+1]-d[i]
// 2.dp[1]=1+k;dp[i]表示di天及之前所有的票全部买完的最小花费
// 3.还是考虑张三处于第d_i(i>1)天时,这一天的票有两种可能:
// ①从第d_i天开始重新买票,此时dp[i]=dp[i-1]+1+k。
// ②将d_i天和前面的是一起买的,既然和前面一起买,那么d_i肯定和d_i-1是一起的,此时花费就相当于在前面d_i-1的基础上多花d[i]-d[i-1]元,此时dp[i]=dp[i-1]+d[i]-d[i-1];
// 既然最终要求的是最小花费,那么我们在这两种可能性之中选择较小值即可。
// 就有了状态转移方程:dp[i]=min(dp[i-1]+1+k,dp[i-1]+d[i]-d[i-1]);
// 即dp[i]=dp[i-1]+min(1+k,d[i]-d[i-1]);
// 4.最终答案即为dp[n]
// #include<cstdio>
// #include<iostream>
// #define ll long long
// using namespace std;
// int n;//看表演的天数
// ll k;//题意中的固定值K
// ll d[100100];//d[]数组用来表示题意中的d1,……dn;
// ll dp[100100];//dp[i]表示di天及之前的最小花费
// int main(){
// freopen("perform.in","r",stdin);
// freopen("perform.out","w",stdout);
// cin>>n>>k;
// for(int i=1;i<=n;i++){
// cin>>d[i];
// }
// dp[1]=1+k;
// for(int i=2;i<=n;i++){
// dp[i]=dp[i-1]+min(1+k,d[i]-d[i-1]);
// }
// cout<<dp[n]<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 也可以从贪心的角度来思考这道题目。
// 对于d_i这一天来说,它要么①重新从这一天开始买票,要么和d_i-1天一起。
// 我们用ans表示d_i之前买票的花费,
// 那么①重新买票的总花费为ans+1+k;②和d_i-1一起的总花费为ans+1。
// 两种比较一下取较小值即可。
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int n;//看表演的天数
ll k;//题意中的K
ll d[100100],ans=0;//ans表示最小花费
int main(){
freopen("perform.in","r",stdin);
freopen("perform.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>d[i];
if(i==1) ans+=1+k;//对于d1,只能从头开始买票,花费为1+k
else{
//d[i]-d[i-1]表示和前面一起买票的花费
//1+k表示重新买票的花费
if(d[i]-d[i-1]>1+k) ans+=1+k;
else ans+=d[i]-d[i-1];
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
// 这道题常规枚举的话比较难以实现,要考虑每个苹果树分多少个篮子,每个篮子分多少苹果,
// 但我们可以观察数据范围0≤K≤2,有部分测试点的,我们可以针对这情况进行讨论获取部分分数,
// 那么当K为0的时候,显然AK汪和AC喵没办法拿到任何苹果,答案为0
// 当K为2的时候,只有两个果篮,这个情况比较容易讨论,我们只需要聚焦于果子数目最多的两棵树即可,
// 设最多的果子数目b1,次多的b2, 讨论按照[b1,b2]形式和[b1,b1/2]形式 哪一种获得的最多,那么很容易的可以写出代码。
// #include <bits/stdc++.h>
// using namespace std;
// int b[1010];
// bool cmp(int x, int y){
// return x>y;
// }
// int main(){
// freopen("mimi.in","r",stdin);
// freopen("mimi.out","w",stdout);
// int n,k;
// cin>>n>>k;
// for(int i=1;i<=n;i++){
// cin>>b[i];
// }
// if(k==0){
// cout<<0;
// return 0;
// }
// sort(b+1,b+n+1,cmp);
// cout<<max(b[2] , b[1]/2);
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 100 90 取90
// 100 40 取100/2=50
// 这道题直接枚举比较困难,我从问题本身来看,在K个果篮取完后,我们把篮子按苹果数目从小到大排序之后,因为AC喵会拿走苹果数量较多k/2的个篮子给自己
// 所以前K/2个篮子是AK狗的,后K/2个篮子是AC喵的 ,那要使得前K/2个篮子的苹果数目和最大,就需要让他的和与后面K/2个篮子苹果数目之和尽可能接近,
// 1 2 3 4 5 ||| 6 7 8 9 10
// 让前K/2个篮子的和与后面K/2个篮子苹果数目之和尽可能接近,这个问题可以转换为让后K/2个篮子的苹果数目之和尽可能小,
// 在图中排序后半部分的最小数字所在的位置为6,设位置6的数字为x,不难发现后面的数字都为x的时候和才最小,也就是苹果最多的K/2个篮子的苹果数目相同时最小。
// 有了这个条件之后,我们就可以以此为突破口,枚举最多的K/2个篮子的每个篮子的苹果数目i,i最大不会超过每颗树最多的苹果数目1000
// 判断以该分配方法下,较少的K/2个篮子如何获得最大苹果数目,考虑贪心的思想,较少的K/2个篮子苹果数目都为i时,我们就可以获得最大的苹果数目
// 那我们尽量让较少的K/2个篮子分得i个数目的苹果,如果不能全部分得,那么就从每颗树的苹果按照i一蓝子分出去剩余的苹果中,选取较大值。然后在枚举i的过程中维护一个最大果子和即可。
// 针对每个枚举出的数目 i 计算以当前的数目分得的篮子数目,并用优先队列存储每颗树按照i个分出去剩余的部分。
// int cnt = 0; //计数按照i个苹果每篮子,分出的篮子数目
// //优先队列,存储每棵树按照i个苹果每篮子,分出后剩余不可分的果子数,大的在队首
// priority_queue<int> q;
// for(int j=1;j<=n;j++){
// cnt += b[j]/i; //计数分出蓝子数目
// q.push(b[j]%i);
// }
// 对于计算出的篮子数目cnt有三中情况:
// ● 按照 i 个一蓝子分不出K/2个给AC喵
// ● 按照 i 个一蓝子分出的个数不低于K个
// ● 按照 i 个一蓝子分出的个数大于等于 K/2 小于 K
// //三种情况
// if(cnt<k/2) continue; //分不出k/2个给AC喵
// else if(cnt>=k){ //以i为每一蓝子的数目,可以分k个
// ans = max(ans , i*k/2);
// break;
// }
// else{ //分不到k个,看差多少从优先队列中取出给AK汪
// int sum = (cnt-k/2)*i;
// //剩余k-cnt 个篮子
// int rem = k-cnt;
// while(rem--){
// sum += q.top();
// q.pop();
// }
// ans = max(ans , sum);
// }
#include <bits/stdc++.h>
using namespace std;
int b[1010];
int main(){
freopen("mimi.in","r",stdin);
freopen("mimi.out","w",stdout);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>b[i];
}
int ans = 0;
for(int i=1000;i>=1;i--){
int cnt = 0; //计数按照i个苹果每篮子,分出的篮子数目
//优先队列,存储每棵树按照i个苹果每篮子,分出后剩余不可分的果子数,大的在队首
priority_queue<int> q;
for(int j=1;j<=n;j++){
cnt += b[j]/i; //计数分出蓝子数目
q.push(b[j]%i);
}
if(cnt<k/2) continue; //分不出k/2个给AC喵
//两种情况,以i为每一蓝子的数目,可以分k个
if(cnt>=k){
ans = max(ans , i*k/2);
break;
}
//分不到k个,看差多少从优先队列中取出
else{
int sum = (cnt-k/2)*i;
//剩余k-cnt 个篮子
int rem = k-cnt;
while(rem--){
sum += q.top();
q.pop();
}
ans = max(ans , sum);
}
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
// 直接枚举修改所有的字符,每一个字符修改之后都重新计算一下当前设计序列可以命中的靶子数量。
// tips1:这里因为代码中多处需要计算命中的靶子数量。所以可以将这部分代码写到函数里面。
// tips2:因为有可能会坐标有可能是负数,使用数组标记时不方便,所以可以将所有的坐标统一加100000。
// #include<cstdio>
// #include<cstring>
// #include<iostream>
// #define ll long long
// using namespace std;
// int T,C;
// bool ini_v[200100],v[200100];//ini_v[i]=1表示位置i有靶子,v[i]=1表示位置i的靶子被打过了。
// char s[100100];//字符序列
// int ans;//用来存储最终答案
// int cal(){//用来计算当前的S序列的命中数量
// memcpy(v,ini_v,sizeof(v));//因为函数中要对v数组进行修改,所以每次都要重新初始化
// int loc=100000;//张三的起始位置0+100000
// int sum=0; //统计命中靶子数量
// for(int i=1;i<=C;i++){//遍历射击序列来进行数量计算
// if(s[i]=='L') loc--;//左移
// if(s[i]=='R') loc++;//右移
// if(s[i]=='F'){//射击
// if(v[loc]==1){//只有当前位置是靶子才能射击
// sum++;
// v[loc]=0;//一个靶子只能射击一次,所以射击后标记为0
// }
// }
// }
// return sum;
// }
// int main(){
// freopen("sharpshooter.in","r",stdin);
// freopen("sharpshooter.out","w",stdout);
// cin>>T>>C;
// for(int i=1;i<=T;i++){
// int x;
// cin>>x;
// x+=100000;//因为位置有可能是负数,不能使用数组标记,所以所有的位置全部+100000
// ini_v[x]=1;
// }
// cin>>(s+1);
// //计算0次修改的时候,命中靶子的数量
// ans=cal();
// for(int i=1;i<=C;i++){
// char tmp=s[i];
// s[i]='F';//修改成F
// ans=max(ans,cal());//计算当前命中数量并和ans比较
// s[i]='L';//修改成L
// ans=max(ans,cal());//计算当前命中数量并和ans比较
// s[i]='R';//修改成R
// ans=max(ans,cal());//计算当前命中数量并和ans比较
// s[i]=tmp;
// }
// cout<<ans<<endl;
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 其实,修改一个字符之后,产生的影响就是后面的F射击时的位置(不一定射中靶子)发生了变化。
// 比如,将 LF R RFRF 修改成 LF L RFRF
// L(-1)->F(-1)->R(0)->R(1)->F(1)->R(2)->F(2)
// 射击位置分别为-1,1,2
// L(-1)->F(-1)->L(-2)->R(-1)->F(-1)->R(0)->F(0)
// 射击位置分别为-1,-1,0
// 将R修改成L,导致蓝色部分之后的所有射击位置整体左移了2位,即整体-2。
// ①L->R 相当于 将所有该字符之后的射击位置向后移动2位,也就是+2。
// ②L->F 相当于 将所有该字符之后的射击位置向后移动1位,也就是+1,同时增加一个射击位
// ③R->L 相当于 将所有该字符之后的射击位置向前移动2位,也就是-2
// ④R->F 相当于 将所有该字符之后的射击位置向前移动1位,也就是-1,同时增加一个射击位
// ⑤F->L 相当于 将所有该字符之后的射击位置向前移动1位,也就是-1,同时减少一个射击位
// ⑥F->R 相当于 将所有该字符之后的射击位置向后移动1位,也就是+1,同时减少一个射击位
// 如果只考虑位置变化,其实只有+1,-1,+2,-2四种情况
// 其中②和④,因为是修改成F,所以在射击位置移动的同时,还会增加一个射击位
// ⑤和⑥,因为将F修改成其他,所以在设计位置移动的同时,还会减少一个射击位。
// 3)我们可以将不做修改的射击位置和整体移动(+1,-1,+2,-2四种情况)的射中靶子的射击位置全部预处理出来,并分别存储5个set集合当中。
// 同时,由于一个位置有可能被多次射击,所以再用5个cnt数组去统计每个位置出现的次数。
// int loc=100010;//用来表示张三所处的位置
// //整体移动2,1,-2,-1并将其对应的射击位置保存到set中
// for(int i=1;i<=C;i++){
// if(s[i]=='L') loc--;//向左移动
// else if(s[i]=='R') loc++;//向右移动
// else if(s[i]=='F'){//射击
// if(ini_v[loc]==1) se[0].insert(loc),cnt[0][loc]++;//不做修改的情况,如果当前位置有靶子,则保存该位置
// if(ini_v[loc+2]==1) se[1].insert(loc+2),cnt[1][loc+2]++;// 整体+2
// if(ini_v[loc+1]==1) se[2].insert(loc+1),cnt[2][loc+1]++;// 整体+1
// if(ini_v[loc-2]==1) se[3].insert(loc-2),cnt[3][loc-2]++;// 整体-2
// if(ini_v[loc-1]==1) se[4].insert(loc-1),cnt[4][loc-1]++;// 整体-1
// }
// }
// 假设我们修改的是某个位置i的字符,那么位置i之前的射击位置是不变的;位置i之后是整体移动(-1,+1,-2,或+2)的。
// 那么答案ans=左边射中的靶子数量+右边射中的靶子数量。
// 然后,我们可以枚举字符序列,列出所有的修改情况并找出最大射击靶子的数量。不做修改的情况,可以作为我们的答案ans的初始值
// 对于左边的部分,我们可以重复前面逐个处理字符序列的过程,即可得到左边部分的射击靶子数。
// 对于右边的部分,我们可以从预处理的se[1~4]获取,根据当前字符的值来判断使用哪几个集合。
// 因为有的F会从随着i的增大从右半部分变为左半部分,所以我们需要及时将不属于右半部分的靶子从se[1~4]中删除。
// //枚举答案
// loc=100010;//张三初始位置
// ans=se[0].size();//不做修改的情况作为初始ans
// se[0].clear();//枚
// for(int i=1;i<=C;i++){
// if(s[i]=='L'){//当前字符为L,有两种修改方式。
// //L->R
// ans=max(ans,(int)(se[0].size()+se[1].size()));//左边+右边
// //L->F
// int tmp=0;
// //修改成F,增加一个射击位置
// // (当前位置有靶子 并且 左右两边都没有射击过该靶子 才可以)
// if(ini_v[loc]&&!se[0].count(loc)&&!se[2].count(loc)) tmp=1;
// ans=max(ans,(int)(se[0].size()+tmp+se[2].size()));//左边+新靶子+右边
// loc--;
// }
// else if(s[i]=='R'){// 当前字符为R(基本同字符为L的情况)
// //R->L
// ans=max(ans,(int)(se[0].size()+se[3].size()));
// //R->F
// int tmp=0;
// if(ini_v[loc]&&!se[0].count(loc)&&!se[4].count(loc)) tmp=1;//修改成F,增加一个射击位置
// ans=max(ans,(int)(se[0].size()+tmp+se[4].size()));
// loc++;
// }
// else if(s[i]=='F'){
// //因为要将F修改为L或R,所以会减少一个射击位置
// if(--cnt[1][loc+2]<=0) se[1].erase(loc+2); //如果loc+2这个位置只出现过一次,则在se[1]中将其删除
// if(--cnt[2][loc+1]<=0) se[2].erase(loc+1); //如果loc+1这个位置只出现过一次,则在se[2]中将其删除
// if(--cnt[3][loc-2]<=0) se[3].erase(loc-2); //如果loc-2这个位置只出现过一次,则在se[3]中将其删除
// if(--cnt[4][loc-1]<=0) se[4].erase(loc-1); //如果loc-1这个位置只出现过一次,则在se[4]中将其删除
// ans=max(ans,(int)(se[0].size()+se[4].size())); //修改成L,左边+右边
// ans=max(ans,(int)(se[0].size()+se[2].size())); //修改成R,左边+右边
// if(ini_v[loc]==1) se[0].insert(loc);
// //当前这个loc位置如果有靶子,一定会在se[0]里面 ,所以需要将其他几个集合中的loc删掉,避免重复计算
// se[1].erase(loc);
// se[2].erase(loc);
// se[3].erase(loc);
// se[4].erase(loc);
// }
// }
#include<bits/stdc++.h>
using namespace std;
int T,C;
bool ini_v[200100];
set<int>se[10];
int cnt[10][200100];
char s[100100];
int ans;
/*
1 l->r 将后面所有的射击位置移 2 位
2 l->f 将后面所有的射击位置移 1 位,并增加一个射击位
3 r->l 将后面所有的射击位置移 -2位
4 r->f 将后面所有的射击位置移 -1位,并增加一个射击位
4 f->l 将后面所有的射击位置移 -1位,并减少一个射击位
2 f->r 将后面所有的射击位置移 1位,并减少一个射击位
位置变化其实一共只有2,1,-2,-1四种情况s
*/
int main(){
freopen("sharpshooter.in","r",stdin);
freopen("sharpshooter.out","w",stdout);
cin>>T>>C;
for(int i=1;i<=T;i++){
int x;
cin>>x;
x+=100010;
ini_v[x]=1;//标记所有的靶子
}
cin>>(s+1);
int loc=100010;//用来表示张三所处的位置
//整体移动2,1,-2,-1并将其对应的射击位置保存到set中
for(int i=1;i<=C;i++){
if(s[i]=='L') loc--;//向左移动
else if(s[i]=='R') loc++;//向右移动
else if(s[i]=='F'){//射击
if(ini_v[loc]==1) se[0].insert(loc),cnt[0][loc]++;//不做修改的情况,如果当前位置有靶子,则保存该位置
if(ini_v[loc+2]==1) se[1].insert(loc+2),cnt[1][loc+2]++;// 整体+2
if(ini_v[loc+1]==1) se[2].insert(loc+1),cnt[2][loc+1]++;// 整体+1
if(ini_v[loc-2]==1) se[3].insert(loc-2),cnt[3][loc-2]++;// 整体-2
if(ini_v[loc-1]==1) se[4].insert(loc-1),cnt[4][loc-1]++;// 整体-1
}
}
//枚举答案
loc=100010;//张三初始位置
ans=se[0].size();//不做修改的情况作为初始ans
se[0].clear();//枚
for(int i=1;i<=C;i++){
if(s[i]=='L'){//当前字符为L,有两种修改方式。
//L->R
ans=max(ans,(int)(se[0].size()+se[1].size()));//左边+右边
//L->F
int tmp=0;
//修改成F,增加一个射击位置
// (当前位置有靶子 并且 左右两边都没有射击过该靶子 才可以)
if(ini_v[loc]&&!se[0].count(loc)&&!se[2].count(loc)) tmp=1;
ans=max(ans,(int)(se[0].size()+tmp+se[2].size()));//左边+新靶子+右边
loc--;
}
else if(s[i]=='R'){// 当前字符为R(基本同字符为L的情况)
//R->L
ans=max(ans,(int)(se[0].size()+se[3].size()));
//R->F
int tmp=0;
if(ini_v[loc]&&!se[0].count(loc)&&!se[4].count(loc)) tmp=1;//修改成F,增加一个射击位置
ans=max(ans,(int)(se[0].size()+tmp+se[4].size()));
loc++;
}
else if(s[i]=='F'){
//因为要将F修改为L或R,所以会减少一个射击位置
if(--cnt[1][loc+2]<=0) se[1].erase(loc+2); //如果loc+2这个位置只出现过一次,则在se[1]中将其删除
if(--cnt[2][loc+1]<=0) se[2].erase(loc+1); //如果loc+1这个位置只出现过一次,则在se[2]中将其删除
if(--cnt[3][loc-2]<=0) se[3].erase(loc-2); //如果loc-2这个位置只出现过一次,则在se[3]中将其删除
if(--cnt[4][loc-1]<=0) se[4].erase(loc-1); //如果loc-1这个位置只出现过一次,则在se[4]中将其删除
ans=max(ans,(int)(se[0].size()+se[4].size())); //修改成L,左边+右边
ans=max(ans,(int)(se[0].size()+se[2].size())); //修改成R,左边+右边
if(ini_v[loc]==1) se[0].insert(loc);
//当前这个loc位置如果有靶子,一定会在se[0]里面 ,所以需要将其他几个集合中的loc删掉,避免重复计算
se[1].erase(loc);
se[2].erase(loc);
se[3].erase(loc);
se[4].erase(loc);
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
// // 1) 直接把所有的边都存下来。
// // 2)用dis[i]表示到达城市i的最短时间(初始时,dis[1]=0,其余的dis[i]均为极大值)
// // 3)不断用这m条边去更新到达每个城市的最短时间。
// // 更新时,需要根据题意来做点变动:
// // ①首先要判断当前是否能够上去飞机,如果上不去直接跳过。
// // ②因为 s 是到达时间,所以直接将s 和dis[d]进行比较。
// #include<bits/stdc++.h>
// using namespace std;
// int n,m;
// struct edge{
// int c,r,d,s;
// };
// edge e[200100];
// int a[200100];//停泊时间
// int dis[200100];//dis[i]表示起点到达点i的最早时间
// int main(){
// freopen("travel.in","r",stdin);
// freopen("travel.out","w",stdout);
// cin>>n>>m;
// for(int i=1;i<=m;i++)
// {
// cin>>e[i].c>>e[i].r>>e[i].d>>e[i].s;
// }
// for(int i=1;i<=n;i++){
// cin>>a[i];
// }
// memset(dis,0x3f,sizeof(dis));//将到达所有城市的时间初始化为极大值
// dis[1]=0; //到达起点的时间为0
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// int c=e[j].c,r=e[j].r,d=e[j].d,s=e[j].s;
// int wait=0;
// if(c!=1) wait=a[c];//计算停泊时间,起点1不用停泊
// if(dis[c]+wait>r) continue;//如果不能进入飞机,则跳过
// if(dis[d]>s) dis[d]=s;//更新到达城市d的时间
// }
// }
// for(int i=1;i<=n;i++){
// if(dis[i]==dis[0]) cout<<-1<<endl;
// else cout<<dis[i]<<endl;
// }
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 用领接表,从1号城市开始dfs
// 对于每一个点城市点x,枚举x的相邻点y,是否可以通过点x更早到达y
// 判断条件:
// 1.在规定时间之前进入该城市的灰机;
// 2.该航线到达目标城市的时间更早。
// #include<bits/stdc++.h>
// using namespace std;
// int n,m;
// struct edge{
// int c,r,d,s,id;
// };
// vector<edge> ve[200100];//邻接表存图,ve[x]存的是所有从x出发的航线
// int a[200100];//停泊时间
// int dis[200100];//dis[i]表示起点到达点i的最早时间
// bool vis[200100];
// bool cmp(edge a,edge b){
// return a.r>b.r;
// }
// void dfs(int x){//搜索当前点x
// int t = dis[x];
// /*
// 必须要用变量t保存一下时间;
// 如果后面直接用dis[x]的话,有可能在之后的搜索过程中
// 再回到x点并修改dis[x]的值,从而导致代码超时
// */
// for(int i=0;i<ve[x].size();i++){
// int y=ve[x][i].d,r=ve[x][i].r,s=ve[x][i].s,id=ve[x][i].id;
// int wait=0;
// if(x!=1) wait=a[x];//x==1时在起点位置,不需要停泊
// if(t+wait>r) break;
// if(t+wait<=r&&dis[y]>s){
// //可以在规定时间前进入飞机 并且 到达城市y的时间更早
// vis[id]=1;
// dis[y]=s;
// dfs(y);
// }
// }
// }
// int main(){
// freopen("travel.in","r",stdin);
// freopen("travel.out","w",stdout);
// cin>>n>>m;
// for(int i=1;i<=m;i++)
// {
// int c,r,d,s;
// cin>>c>>r>>d>>s;
// ve[c].push_back((edge){c,r,d,s,i});//存图
// }
// for(int i=1;i<=n;i++){
// cin>>a[i];
// sort(ve[i].begin(),ve[i].end(),cmp);
// }
// memset(dis,0x3f,sizeof(dis));//将所有dis初始化为极大值
// dis[1]=0; //到达起点的时间为0
// dfs(1);
// fclose(stdin);
// fclose(stdout);
// return 0;
// }
// 1)首先,我们可以对每个点的边按照进入飞机的时间(也就是r)从大到小排序。如果当前这条边对应的飞机已经进不去了,那么后面的飞机就更进不去了,就可以直接break;
// 2)对于一条航线来说,如果已经走过了,那么这条航线就不需要再走第二遍了,再走第二遍到达时间也是一样的。所以我们就可以用一个数组start[x]来表示当前点x的这些边应该从第几条开始走。
// 加上这两个剪枝之后,就可以高效通过这个题目了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
int c,r,d,s,id;//航线编号
};
bool cmp(edge a,edge b){
return a.r>b.r;
}
vector<edge> ve[200100];//邻接表存图,ve[x]存的是所有从x出发的航线
int a[200100];//停泊时间
int dis[200100];//dis[i]表示起点到达点i的最早时间
int start[200100];//标记每个点从哪条航线开始搜索
bool vis[200100];
void dfs(int x){//当前搜索点x
int t = dis[x];
/*
必须要用变量t保存一下时间;
如果后面直接用dis[x]的话,有可能在之后的搜索过程中
再回到x点并修改dis[x]的值,从而导致代码超时
*/
for(int i=0;i<ve[x].size();i++){//for(int i=start[x];i<ve[x].size();i++){
int y=ve[x][i].d,r=ve[x][i].r,s=ve[x][i].s,id=ve[x][i].id;
//if(vis[id]) continue;
//start[x]=i;
int wait=0;
if(x!=1) wait=a[x];//x==1时在起点位置,不需要停泊
if(t+wait>r) break;
if(t+wait<=r&&dis[y]>s){
//可以在规定时间前进入飞机 并且 到达城市y的时间更早
vis[id]=1;
dis[y]=s;
dfs(y);
}
}
}
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int c,r,d,s;
cin>>c>>r>>d>>s;
ve[c].push_back((edge){c,r,d,s,i});//存图
}
for(int i=1;i<=n;i++){
cin>>a[i];
sort(ve[i].begin(),ve[i].end(),cmp);
}
memset(dis,0x3f,sizeof(dis));//将所有dis初始化为极大值
dis[1]=0;//0时刻就在城市1
dfs(1);
for(int i=1;i<=n;i++){//for循环输出到达时间
if(dis[i]==dis[0]) cout<<-1<<endl;//无法到达输出-1
else cout<<dis[i]<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
这里空空如也
有帮助,赞一个