P12870 [蓝桥杯 2025 国 Python A] 铺设能源管道
题目描述
能源公司正着手建立新的基地。为了确保基地的能源供应，公司计划铺设一条长度至少为 n 公里的能源管道。铺设管道的成本并非简单地与管道长度成正比，而是由管道长度的各位数字之和决定。例如，铺设 123 公里的管道，实际成本为 1+2+3=6 。
为了尽可能降低成本，公司希望找到一个长度为 m 公里的铺设方案，使得 m 不小于 n，并且 m 的数位和最小。如果存在多个满足条件的 m，则选择数值最小的方案，以确保在成本相同的情况下，尽可能减少资源浪费。
现在，请你帮助能源公司计算出最优的管道铺设长度 m。
输入格式
输入一行包含一个整数 n，表示需要铺设的最低管道长度。
输出格式
输出一行包含一个整数 m，表示最优的管道铺设长度。
输入输出样例
输入 #1复制
9
输出 #1复制
10
说明/提示
【评测用例规模与约定】
对于 30% 的评测用例，1≤n≤100。
对于所有的评测用例，1≤n≤109。
这题我想到用字符串，这样直接能知道n是几位数，不用慢慢数。
#include<iostream> #include<string> using namespace std; //如果是1后面跟x个0的形式，已经是最小长度了，直接输出即可 bool check(string n) { if(n[0]!='1') return false; for(int i=1;i<n.size();i++) { if(n[i]!='0') return false; } return true; } int main() { string n; cin>>n; if(check(n)==true) cout<<n<<endl; //不是的话就输出：1+位数×0 else { cout<<"1"; for(int i=1;i<=n.size();i++) cout<<"0"; } return 0; }插一句，看到评论区有人打表能AC，莫名有点好笑，简直就是大力出奇迹，代码如下：
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { int n; cin >> n; if (n == 1) cout << 1 << endl; else if (n <= 10) cout << 10 << endl; else if (n <= 100) cout << 100 << endl; else if (n <= 1000) cout << 1000 << endl; else if (n <= 10000) cout << 10000 << endl; else if (n <= 100000) cout << 100000 << endl; else if (n <= 1000000) cout << 1000000 << endl; else if (n <= 10000000) cout << 10000000 << endl; else if (n <= 100000000) cout << 100000000 << endl; else if (n <= 1000000000) cout << 1000000000 << endl; return 0; }P1478 陶陶摘苹果（升级版）
题目描述
又是一年秋季时，陶陶家的苹果树结了 n 个果子。陶陶又跑去摘苹果，这次他有一个 a 公分的椅子。当他手够不着时，他会站到椅子上再试试。
这次与 NOIp2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 s 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 s<0 之前最多能摘到多少个苹果。
现在已知 n 个苹果到达地上的高度 xi，椅子的高度 a，陶陶手伸直的最大长度 b，陶陶所剩的力气 s，陶陶摘一个苹果需要的力气 yi，求陶陶最多能摘到多少个苹果。
输入格式
第 1 行：两个数 苹果数 n，力气 s。
第 2 行：两个数 椅子的高度 a，陶陶手伸直的最大长度 b。
第 3 行~第 3+n−1 行：每行两个数 苹果高度 xi，摘这个苹果需要的力气 yi。
输出格式
只有一个整数，表示陶陶最多能摘到的苹果数。
输入输出样例
输入 #1复制
8 15 20 130 120 3 150 2 110 7 180 1 50 8 200 0 140 3 120 2
输出 #1复制
4
说明/提示
对于 100% 的数据，n≤5000, a≤50, b≤200, s≤1000, xi≤280, yi≤100。
在vector里面套pair，sort函数默认先按照第一个元素升序，第一个元素相等再按照第二个元素升序。其实 这题本来我想用map自动排序的功能，但是后面想想发现如果力气相同，新的力气会覆盖旧的力气，不可行。
#include<iostream> #include<vector> #include<algorithm> using namespace std; vector <pair<int, int>> mp; int main() { int n, total_effort, chair_height, arm_len; int cnt = 0; cin >> n >> total_effort >> chair_height >> arm_len; for (int i = 0;i < n;i++) { int height, effort; cin >> height >> effort; mp.push_back({ effort,height }); } //先按照力气升序 //力气相同，再按照高度升序 sort(mp.begin(), mp.end()); for (int i = 0;i < n;i++) { int apple_effort = mp[i].first; int apple_height = mp[i].second; if (total_effort >= apple_effort && chair_height + arm_len >= apple_height) { total_effort = total_effort - apple_effort; cnt++; } } cout << cnt << endl; return 0; }但我这个还不是最好的方法，我写完和科技交流了一下：
先筛选能够到的苹果，再按力气排序
因为有些苹果即使力气小，但高度太高也摘不到
#include<iostream> #include<vector> #include<algorithm> using namespace std; vector <int> e;//effort int main() { int n, total_effort, chair_height, arm_len; int cnt = 0; cin >> n >> total_effort >> chair_height >> arm_len; for (int i = 0;i < n;i++) { int height, effort; cin >> height >> effort; //先筛选能够到的苹果 if (chair_height + arm_len >= height) e.push_back(effort); } //再按力气排序 sort(e.begin(), e.end()); //注意苹果的总数量不一定等于能够到的苹果的数量 //因此这一行应该写size而不是n for (int i = 0;i < e.size();i++) { if (total_effort >= e[i]) { total_effort -= e[i]; cnt++; } } cout << cnt << endl; return 0; }B3637 最长上升子序列
题目描述
这是一个简单的动规板子题。
给出一个由 n(n≤5000) 个不超过 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。
最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。
输入格式
第一行，一个整数 n，表示序列长度。
第二行有 n 个整数，表示这个序列。
输出格式
一个整数表示答案。
输入输出样例
输入 #1复制
6 1 2 4 1 3 4
输出 #1复制
4
说明/提示
分别取出 1、2、3、4 即可。
