头像

bobo_cxy




离线:20小时前



题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。

输入格式
第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式
输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出-1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于0,且不超过10000。

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

思路

Dijkstra 复杂度为O(n^2),当n很大时,就需要优化了,可以使用优先队列priority_queue,能够自动排序,出列的时候的数据就已经是有顺序的了,再将邻接矩阵改为邻接表存储,可以有效节省时间和空间
需要找到最小的距离的节点,所以入队的时候包含两个元素,dis和当前节点,所以用typedef pair<int, int> PII,使用pair捆绑两个整型
使用priority_queue<PII,vector<PII>,greater<PII> > q;定义一个PII型的从小到大的优先对列q

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int, int> PII;
const int N=150010;
int n,m; 
int dis[N]; //记录当前点与第一个点之间的距离  
int h[N];
int e[N];//邻边的另一个端点
int ne[N];//链表的下一个结点下标
int w[N];//邻边的长度
int idx=0;
int vis[N];

int dijkstra()
{
    memset(dis,0x3f,sizeof(dis));//本题要求最小值,初始化为极大值 
    dis[0]=1;
    priority_queue<PII,vector<PII>,greater<PII> > q;
    q.push({0,1});//距离为0,第1个点
    while(q.size()){
        PII temp=q.top();
        q.pop();
        int d=temp.second;
        int distance=temp.first;
        if(!vis[d]){
            vis[d]=1;
            for(int i=h[d];i!=-1;i=ne[i]){
                int j=e[i];
                if(dis[j]>distance+w[i]){
                    dis[j]=distance+w[i];
                    q.push({dis[j],j});
                }
            }
        }
    } 
    if(dis[n]==0x3f3f3f3f){//最终一个点到第一个点的距离无穷大,即不存在最短路径 
        return -1;
    }
    else{
        return dis[n];//第n个点到第一个点之间的距离 
    }
}
int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof(h));//初始化为无穷大 
    while(m--){
        int x,y,z;
        cin >> x >> y >> z;
        w[idx] = z; 
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx++;
    }
    cout << dijkstra() << endl;
    return 0;
 } 




题目描述

给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。

输入格式
第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式
输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出-1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

思路

Dijkstra算法算是贪心思想实现的,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离
本题要求我们求出从1号点到n号点的最短距离,也就是需要我们来求解dist[n]的最小值。
通过一步步的求出从1到各个点的最小值,也就是数组dist的所有的值,即可求出结果
如何求dist:
因为要求最小值,所以先将数组初始化为极大值,
从1开始,对于每一个点i,访问1~n每个点k,如果当前访问的点没有被访问过,并且距离更小,就存入,直到把所有n个点遍历完之后得到的就是最短的对于的点,即点i到起点的最短路径
每次找到最小距离对应的点k时,都要更新disdis[j]=min(dis[j],dis[k]+g[k][j])

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=505;
int n,m; 
int g[N][N];//存储邻接矩阵 
int dis[N]; //记录当前点与第一个点之间的距离 
int vis[N]; //标记是否已经被选过 

int dijkstra()
{
    memset(dis,0x3f,sizeof(dis));//本题要求最小值,初始化为极大值 
    dis[1]=0;//第一个点是起始点,距离为0
    for(int i=1;i<=n;i++){ 
        int k=0;//存访问的点 
        for(int j=1;j<=n;j++){
            if(!vis[j] && (k==0 || dis[j]<dis[k])){//这个点没有被选过 并且( 是刚开始找点或者距离更小) 
                k=j; // 把当前访问的点存下来 
            }
        }
        vis[k]=1;// 最终选择的下一个点 标记已选 
        for(int j=1;j<=n;j++){//找到了距离最小的点k,并用最小的点k去更新其他的点到起点的距离 
            dis[j]=min(dis[j],dis[k]+g[k][j]);
        }
    } 
    if(dis[n]==0x3f3f3f3f){//最终一个点到第一个点的距离无穷大,即不存在最短路径 
        return -1;
    }
    else{
        return dis[n];//第n个点到第一个点之间的距离 
    }
}
int main()
{
    cin >> n >> m;
    memset(g,0x3f,sizeof(g));//初始化为无穷大 
    while(m--){
        int x,y,z;
        cin >> x >> y >> z;
        g[x][y]=min(g[x][y],z);//有可能有重边,取最小的边长 
    }
    cout << dijkstra() << endl;
    return 0;
 } 




题目描述

把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式
一个整数n。

输出格式
按照从小到大的顺序输出所有方案,每行1个。

首先,同一行相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

数据范围
1≤n≤9

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

对每一个位置的数字进行递归,当数字位数为n时,此时递归x=n+1,输出方案

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[15];
int vis[15];
int res[15];
void dfs(int x){
    if(x==n+1){//n个位子都有数字 
        for(int i=1;i<=n;i++){
            cout << res[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            res[x]=i;//把选择的数存入数组 
            vis[i]=1;//标记已经选择 
            dfs(x+1);//递归下一个位子上的数 
            res[x]=0;//回溯 
            vis[i]=0;//回溯 
        }
    }
}
int main()
{
    cin >> n;   
    dfs(1);//第一个位子上的数字 
    return 0;
}




题目描述

从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。

输入格式
两个整数 n,m ,在同一行用空格隔开。

输出格式
按照从小到大的顺序输出所有方案,每行1个。

首先,同一行内的数升序排列,相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25

输入样例

5 3

输出样例

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

//此题与上题相比,只有递归出口发生了变化

int n,m;
int a[30];//存放数 
int vis[30];//选择为1,不选择为2 ,还没判断为0 
int cnt=0;

void dfs(int x){
    if(x==n+2){
        return;
    }
    if(cnt==m){//一种方案结束 
        for(int i=1;i<=n;i++){
            if(vis[i]==1){//选择的,即是1的输出 
                cout << a[i] << " ";
            }
        }
        cout << endl;
        return;
    }
    vis[x]=1;//选 
    cnt++;
    dfs(x+1);//下一个数 
    vis[x]=0;//回溯 
    cnt--;

    vis[x]=2;//不选 
    dfs(x+1);//下一个数 
    vis[x]=0;//回溯 
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        a[i]=i;//初始化 
    }
    dfs(1);//从数字1开始判断(1~n) 
    return 0;
 } 




题目描述

从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式
输入一个整数n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围
1≤n≤15

输入样例

3

输出样例

3
2
2 3
1
1 3
1 2
1 2 3

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int a[20];//存放数 
int vis[20];//选择为1,不选择为2 ,还没判断为0 

void dfs(int x){
    if(x==n+1){//一种方案结束 
        for(int i=1;i<=n;i++){
            if(vis[i]==1){//选择的,即是1的输出 
                cout << a[i] << " ";
            }
        }
        cout << endl;
        return;
    }
    vis[x]=1;//选 
    dfs(x+1);//下一个数 
    vis[x]=0;//回溯 

    vis[x]=2;//不选 
    dfs(x+1);//下一个数 
    vis[x]=0;//回溯 
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++){
        a[i]=i;//初始化 
    }
    dfs(1);//从数字1开始判断(1~n) 
    return 0;
 } 



活动打卡代码 AcWing 680. 剪绳子

题目描述

有N根绳子,第i根绳子长度为Li,现在需要M根等长的绳子,你可以对N根绳子进行任意裁剪(不能拼接),请你帮忙计算出这M根绳子最长的长度是多少。

输入格式
第一行包含2个正整数N、M,表示原始绳子的数量和需求绳子的数量。

第二行包含N个整数,其中第 i 个整数Li表示第 i 根绳子的长度。

输出格式
输出一个数字,表示裁剪后最长的长度,保留两位小数。

数据范围
1≤N,M≤100000,
0<Li<109

输入样例

3 4
3 5 4

输出样例

2.50

样例解释
第一根和第三根分别裁剪出一根2.50长度的绳子,第二根剪成2根2.50长度的绳子,刚好4根。


C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+5;
int a[N];
int n,m;

bool check(double x){//数量
    int c=0;
    for(int i=1;i<=n;i++){
        c=c+a[i]/x;
        if(c>=m){
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    double l=0;
    double r=a[1];//最大值
    while(l-r<-1e-4){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    printf("%.2lf\n",l) ;
    return 0;
  }  




题目描述

有N根绳子,第i根绳子长度为Li,现在需要M根等长的绳子,你可以对N根绳子进行任意裁剪(不能拼接),请你帮忙计算出这M根绳子最长的长度是多少。

输入格式
第一行包含2个正整数N、M,表示原始绳子的数量和需求绳子的数量。

第二行包含N个整数,其中第 i 个整数Li表示第 i 根绳子的长度。

输出格式
输出一个数字,表示裁剪后最长的长度,保留两位小数。

数据范围
1≤N,M≤100000,
0<Li<109

输入样例

3 4
3 5 4

输出样例

2.50

样例解释
第一根和第三根分别裁剪出一根2.50长度的绳子,第二根剪成2根2.50长度的绳子,刚好4根。


C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+5;
int a[N];
int n,m;

bool check(double x){//数量
    int c=0;
    for(int i=1;i<=n;i++){
        c=c+a[i]/x;
        if(c>=m){
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    double l=0;
    double r=a[1];//最大值
    while(l-r<-1e-4){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    printf("%.2lf\n",l) ;
    return 0;
  }  




题目描述

翰翰和达达饲养了N只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为W,而N只小猫的重量分别是C1、C2……CN。

当然,每辆缆车上的小猫的重量之和不能超过W。

每租用一辆缆车,翰翰和达达就要付1美元,所以他们想知道,最少需要付多少美元才能把这N只小猫都运送下山?

输入格式
第1行:包含两个用空格隔开的整数,N和W。

第2..N+1行:每行一个整数,其中第i+1行的整数表示第i只小猫的重量Ci。

输出格式
输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围
1≤N≤18,
1≤Ci≤W≤108

输入样例

5 1996
1
2
1994
12
29

输出样例

2

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

int n,c;
int a[20];
int res;
int sum[20];//每辆车承载的重量 

bool cmp(int a,int b){
    return a>b;
}
void dfs(int x,int cnt){
    if(cnt>=res){ //方案数大于等于当前最优,不再可能是最优了,减枝  
        return;
    }
    if(x==n+1){//结束 
        res=min(cnt,res);
        return;
    }
    for(int i=1;i<=cnt;i++){//遍历前面的已经有猫的车 
        if(sum[i]+a[x]<=c){ //能一起坐下 
            sum[i]=sum[i]+a[x];//加上重量 
            dfs(x+1,cnt);//没有加车,为下一只猫安排 
            sum[i]=sum[i]-a[x];//回溯 
        }
    }
    cnt++;//加车 
    sum[cnt]=a[x];//新加的这辆车的承载重量为当前猫的重量 
    dfs(x+1,cnt);//又增加了一辆车 
    sum[cnt]=0;//回溯 
} 
int main()
{
    cin >> n >> c;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1,a+1+n,cmp); //从大到小排序
    res=18; //最多18只猫,一只猫一辆车 
    dfs(1,0); //从第一只猫开始,此时车数为0 
    cout << res << endl; 
    return 0;
}




题目描述

在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。

可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。

可以先将1、2堆合并,新堆数目为3,耗费体力为3。

接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。

所以达达总共耗费体力=3+12=15。

可以证明15为最小的体力耗费值。

输入格式
输入包括两行,第一行是一个整数n,表示果子的种类数。

第二行包含n个整数,用空格分隔,第i个整数ai是第i种果子的数目。

输出格式
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。

输入数据保证这个值小于231。

数据范围
1≤n≤10000,
1≤ai≤20000

输入样例

3 
1 2 9 

输出样例

15

思路

每次取最小的两个合并,使用优先队列就可以免去排序,队列里的元素按照顺序出列
直到只有一个元素时,其值即为最小体力消耗值

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    priority_queue<int,vector<int>,greater<int> >q; // 优先队列,按照从小到大的顺序 
    while(n--){
        int x;
        cin >> x;
        q.push(x);
    } 
    int res=0;
    while(q.size()>1){ // 大于等于两个元素 
        //取最小的两个合并 
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        res=res+a+b;
        q.push(a+b);
    }
    cout << res << endl;
    return 0;
 } 




题目描述

给定一个R行C列的矩阵,表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。

当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子:

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9
在给定矩阵中,一条可行的滑行轨迹为24-17-2-1。

在给定矩阵中,最长的滑行轨迹为25-24-23-…-3-2-1,沿途共经过25个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。

输入格式
第一行包含两个整数R和C。

接下来R行,每行包含C个整数,表示完整的二维矩阵。

输出格式
输出一个整数,表示可完成的最长滑雪长度。

数据范围
1≤R,C≤300,
0≤矩阵中整数≤10000

输入样例

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例

25

C++ 代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=305;
int n,m; 
int a[N][N];
int mvx[4]={0,0,-1,1};
int mvy[4]={1,-1,0,0};
int f[N][N];//从i,j出发的所有路径的距离长度的最大值 
int dp(int x,int y){
    if(f[x][y]!=0){
        return f[x][y];
    }
    f[x][y]=1;
    for(int i=0;i<4;i++){ // 遍历四个方向 
        int xx=x+mvx[i]; // 新X 
        int yy=y+mvy[i]; // 新y 
        if(xx>=1 && xx<=n &&yy>=1 &&yy<=m && a[x][y]>a[xx][yy]){ //在整个方格的范围内并且高度减小 
            f[x][y]=max(f[x][y],dp(xx,yy)+1); // 找出最优 
        }
    }
    return f[x][y];
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j]; // 每个点的高度 
        }
    }
    int ans=0; 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,dp(i,j)); // 更新最大值 ,找出最优 
        }
    }
    cout << ans << endl;
    return 0;
 }