我要评论目录
a: 机器人王国里的路径长度
如果只有单个的字母则不必用 map ，直接用 char-'a' 存储到普通数组即可。但是本题应该是不全为单个字母，所以需要用 map 存储。由于任一节点只有一个父节点，那么用数组记录每个节点的父节点即可。如果有多个父节点的话就开一个二维的 map 数组
从子节点开始遍历，直到无父节点则代表找到了首都
#include<bits/stdc++.h>
using namespace std;
map<string,string> par;
map<string,int> len;
// map <string,map<string,int> >mp //二维map数组
signed main(){
int n;cin>>n;
int m = pow(2,n+1)-2;
for(int i=1;i<=m;i++){
string s1,s2;
int temp;
cin>>s1>>s2>>temp;
par[s2] = s1;
len[s2] = temp;
}
string now;cin>>now;
long long ans = 0; //数据量较大，开long long 会比较稳妥
while(par[now].length()>0){
ans += len[now];
now = par[now];
}
cout<<ans;
return 0;
}b: 从源点开始的最短路径
dijkstra 或 floyed 或 dfs
开一个数组存储步数，不可能成为最优解的直接舍弃
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tar;
int mp[210][210]; //地图
//bool pd[210][210]; //这条路是否走过 |致命错误！同一条路可以重复走
long long l[210]; //源点到该点路径长度
// 到另一个点的步数必须小于之前花的步数
void dfs(int now,int len){
if(l[now]==0||len<l[now])
l[now] = len;
if(now==tar){
return;
}
for(int i=1;i<=n;i++){
if(i==now) continue;
if(mp[now][i] == 0) continue;
if(l[i]>len+mp[now][i]|| l[i]==0)
{
dfs(i,len+mp[now][i]);
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x1,x2,x3;
cin>>x1>>x2>>x3;
if(mp[x1][x2]==0||x3<mp[x1][x2]){
mp[x1][x2]=x3;
}
}
cin>>tar;
dfs(1,0);
cout<<l[tar];
return 0;
}c: 最少天数
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <limits>
using namespace std;
// 定义图的边
struct edge {
char destination;
int weight;
};
// 计算完成工程的最短天数
int calculateshortesttime(const unordered_map<char, vector<edge>>& graph) {
unordered_map<char, int> indegree;
unordered_map<char, int> earlieststarttime;
// 统计每个事件的入度
for (const auto& node : graph) {
char currentnode = node.first;
indegree[currentnode] = 0;
earlieststarttime[currentnode] = -1; // 初始化最早开始时间为-1
}
for (const auto& node : graph) {
char currentnode = node.first;
for (const edge& edge : node.second) {
char nextnode = edge.destination;
indegree[nextnode]++;
}
}
// 初始化起点的最早开始时间为0
earlieststarttime['a'] = 0;
// 使用拓扑排序计算每个事件的最早开始时间
queue<char> q;
q.push('a');
while (!q.empty()) {
char currentnode = q.front();
q.pop();
auto it = graph.find(currentnode);
if (it == graph.end()) {
continue;
}
for (const edge& edge : it->second) {
char nextnode = edge.destination;
int nextstarttime = earlieststarttime[currentnode] + edge.weight;
earlieststarttime[nextnode] = max(earlieststarttime[nextnode], nextstarttime);
if (--indegree[nextnode] == 0) {
q.push(nextnode);
}
}
}
// 返回工程的最短天数
return earlieststarttime['z'];
}
int main() {
int n, m;
cin >> n >> m;
unordered_map<char, vector<edge>> graph;
// 读取子任务信息
for (int i = 0; i < m; ++i) {
char startnode, endnode;
int weight;
cin >> startnode >> endnode >> weight;
graph[startnode].push_back({ endnode, weight });
}
int shortesttime = calculateshortesttime(graph);
cout << shortesttime << endl;
return 0;
}d: 寻找第二小的数
sort
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tar;
signed main(){
int c;cin>>c;
while(c--){
int n;cin>>n;
int a[110];
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
bool pd = 0;
for(int i=2;i<=n;i++){
if(a[i]!=a[1]){
cout<<a[i]<<endl;
pd = 1;
break;
}
}
if(pd==0) cout<<"no\n";
}
return 0;
}
e: 按十进制各位和排序
自定义一个cmp，sort
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int n = 1000010;
int a[n];
bool cmp(int m,int n){
int x=m,y=n;
int sm=0,sn=0;
while(m>0){
sm+=m%10;
m/=10;
}
while(n>0){
sn+=n%10;
n/=10;
}
if(sm>sn) return 1;
else if(sm==sn) return x>y;
else return 0;
}
signed main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
cout<<a[i]<<' ';
}
return 0;
}
f: 奇偶数的排序
sort
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int n = 100010;
bool cmp(int m,int n){
return m>n;
}
int n,m,tar;
int a[10010];
int odd[n];
int even[n];
signed main(){
int oi=1,ei=1;
for(int i=1;i<=10;i++){
cin>>a[i];
if(a[i]%2) odd[oi++] = a[i];
else even[ei++] = a[i];
}
sort(odd+1,odd+6,cmp);
for(int i=1;i<=5;i++){
cout<<odd[i]<<' ';
}
sort(even+1,even+6);
for(int i=1;i<=5;i++)cout<<even[i]<<' ';
return 0;
}
发表评论