如何做网站规范,网络营销乐云seo,网站查找工具,网站友情链接出售【算法1-2】排序 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 鄙人不才#xff0c;刷洛谷#xff0c;迎蓝桥#xff0c;【算法1-2】排序 已刷#xff0c;现将 AC 代码献上#xff0c;望有助于各位 P1271 选举学生会
【深基9.例1】选举学生会 - 洛谷
题目 解答…【算法1-2】排序 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 鄙人不才刷洛谷迎蓝桥【算法1-2】排序 已刷现将 AC 代码献上望有助于各位 P1271 选举学生会
【深基9.例1】选举学生会 - 洛谷
题目 解答
思路
将候选人编号及其获得的票数映射到一个一维数组上即依据候选人编号对票数进行排序然后根据获得的票数输出编号如a 号 获得 b 票则输出 b 个 a
代码
#includeiostream
using namespace std;
int ren[1005] { 0 };
int n;
int m;
int main() {cin n m;int piao;for (int i 1; i m; i) {cin piao;ren[piao];}for (int i 1; i n; i) {if(ren[i]!0)for (int j 0; j ren[i]; j) {cout i ;}}return 0;
}
P1177 排序
【模板】排序 - 洛谷
题目 解答
思路
快排和归并排序模板均可解决
代码
//快排
#includeiostream
#includealgorithm
using namespace std;
int n;
int a[100005];
void quick_sort(int a[], int l, int r) {if (l r)return;int base a[l r 1], i l - 1, j r 1;while (i j) {do i; while (a[i] base);do j--; while (a[j] base);if (i j)swap(a[i], a[j]);}quick_sort(a, l, j);quick_sort(a, j 1, r);
}
int main() {cin n;for (int i 0; i n; i) cin a[i];quick_sort(a, 0, n - 1);for (int i 0; i n - 1; i)cout a[i] ;cout a[n - 1] endl;return 0;
}//归并排序
#includeiostream
using namespace std;
int n;
int a[100005], tmp[100005];
void merge_sort(int a[], int l, int r) {if (l r)return;int mid (l r) / 2;merge_sort(a, l, mid);merge_sort(a, mid 1, r);int k 0, i l, j mid 1;while (i mid j r) {if (a[i] a[j]) {tmp[k] a[i];k;i;}else {tmp[k] a[j];k;j;}}while (i mid) {tmp[k] a[i];k;i;}while (j r) {tmp[k] a[j];k;j;}for (int i l, j 0; i r; i, j)a[i] tmp[j];
}
int main() {cin n;for (int i 0; i n; i)cin a[i];merge_sort(a, 0, n - 1);for (int i 0; i n; i)cout a[i] ;cout endl;return 0;
}
P1059 明明的随机数
[NOIP2006 普及组] 明明的随机数 - 洛谷
题目 解答
思路
使用数组映射产生的随机数数组元素的下标表示产生的随机数对应的数组元素表示该数的个数
代码
#includeiostream
using namespace std;
int N;
int num[1005] { 0 };
int a[105];
int main() {cin N;for (int i 0; i N; i) {cin a[i];num[a[i]];}int q 0;int b[100];for (int i 1; i 1000; i) {if (num[i] ! 0) {b[q] i;q;} }cout q endl;for (int i 0; i q; i)cout b[i] ;return 0;
}
P1923 求第 k 小的数
【深基9.例4】求第 k 小的数 - 洛谷
题目 解答
思路
使用 nth_element
当采用默认的升序排序规则时nth_element()可以从某个序列中找到第 n 小的元素 K并将 K 移动到序列中第 n 的位置且整个序列经过此函数处理后所有位于 K 之前的元素都比 K 小所有位于 K 之后的元素都比 K 大
快排二分
快排一次将数组分为三个区间分别是小于基准数、等于基准数、大于基准数三个部分根据 k 与 i 和 j 的关系确定下一次递归的区间
代码
//使用nth_element()
#includeiostream
#includealgorithm
#includecstdio
using namespace std;
int n;
int k;
const int N 5e6 100;
int a[N];
int main() {scanf(%d%d,n,k);for (int i 0; i n; i)scanf(%d,a[i]);nth_element(a, a k, a n);printf(%d,a[k]);return 0;
}
P1093 奖学金
[NOIP2007 普及组] 奖学金 - 洛谷
题目 解答
思路
写一个比较函数即可
代码
#includeiostream
#includealgorithm
using namespace std;
typedef struct student {int num;int ch;int ma;int eng;int sum 0;
}student;
bool cmp(student s1, student s2) {if (s1.sum ! s2.sum)return s1.sum s2.sum;else {if (s1.ch ! s2.ch)return s1.ch s2.ch;elsereturn s1.num s2.num;}
}
int main() {int n;cin n;student stu[305];for (int i 0; i n; i) {cin stu[i].ch;cin stu[i].ma;cin stu[i].eng;stu[i].num i 1;stu[i].sum stu[i].ch stu[i].ma stu[i].eng;}sort(stu, stu n, cmp);for (int i 0; i 5; i) {cout stu[i].num stu[i].sum endl;}return 0;
}
P1781 宇宙总统
宇宙总统 - 洛谷
题目 解答
思路
因为票数很大位数很长所以可以用一个字符串表示票数先比较票数的位数位数相同时比较字典序
代码
#includeiostream
#includestring
using namespace std;
typedef struct ren {int num;string piao;int len;
}ren;
int main() {ren r[22];int n;cin n;ren max;max.len 0;for (int i 0; i n; i) {r[i].num i 1;cin r[i].piao;r[i].len r[i].piao.size();if (r[i].len max.len) {max.len r[i].len;max.num r[i].num;max.piao r[i].piao;}else if (r[i].len max.len r[i].piaomax.piao) {max.len r[i].len;max.num r[i].num;max.piao r[i].piao;}}cout max.num endl;cout max.piao endl;return 0;
}
P2676 Bookshelf B
[USACO07DEC] Bookshelf B - 洛谷
题目 解答
思路
因为要使叠加的奶牛的数量最少所以先选择身高高的奶牛叠加故而将奶牛由高到低排序
代码
#includeiostream
#includealgorithm
using namespace std;
int N, B;
int H[20005];
bool cmp(int a, int b) {return a b;
}
int main() {int ans 0, sum 0;cin N B;for (int i 0; i N; i)cin H[i];sort(H, H N, cmp);while (sum B) {sum H[ans];ans;}cout ans;return 0;
}
P1116 车厢重组
车厢重组 - 洛谷
题目 解答
思路
冒泡排序中数值交换的次数
代码
#includeiostream
using namespace std;
int main() {int N;int ans 0;cin N;int t[10010];for (int i 0;i N;i)cin t[i];for (int i 0;i N;i) {for (int j 0;j i;j) {if (t[j] t[i])ans;}}cout ans endl;return 0;
}
P1152 欢乐的跳
欢乐的跳 - 洛谷
题目 解答
思路
依次计算两个连续元素之间差的绝对值排序与 1 ~ n-1 比较
PS第一次使用映射记录两个连续元素之间差的绝对值但是没有通过因为两个数之间的差可能比1000大所以将差映射到0~1000的数组内差大于1000的无法实现映射
代码
#includeiostream
#includecmath
#includealgorithm
using namespace std;
int n;
int a[1005];
int b[1005];
int main() {bool ans true;cin n;for (int i 0; i n; i)cin a[i];for (int i 0; i n - 1; i)b[i] abs(a[i] - a[i 1]);sort(b, b n - 1);for (int i 0; i n-1; i) {if (b[i] ! i 1) {ans false;break;}}if (ans)cout Jolly endl;elsecout Not jolly endl;return 0;
}
P1068 分数线划定
[NOIP2009 普及组] 分数线划定 - 洛谷
题目 解答
思路
根据要求排序然后确定面试分数线检查重分人员重新计算实际进入面试的人数
代码
#includeiostream
#includecmath
#includealgorithm
using namespace std;
int n, m;
typedef struct stu {int num;int grade;
}stu;
bool cmp(stu a, stu b) {if (a.grade b.grade)return a.num b.num;return a.grade b.grade;
}
int main() {cin n m;stu s[5005];for (int i 0; i n; i) cin s[i].num s[i].grade;int ans floor(m * 1.5);//向下取整int ans_s ans;sort(s, s n, cmp);for (int i ans; i n; i) {//判断是否有重分if (s[i].grade ! s[ans - 1].grade)break;else ans_s;}cout s[ans - 1].grade ans_s endl;for (int i 0; i ans_s; i)cout s[i].num s[i].grade endl;return 0;
}P5143 攀爬者
攀爬者 - 洛谷
题目 解答
思路
先根据 z 坐标将所有的点排序然后依次通过所有点并计算距离
代码
#includeiostream
#includealgorithm
#includecmath
using namespace std;
int N;
typedef struct dian {int x;int y;int z;bool state false;
}dian;
bool cmp(dian a, dian b) {return a.z b.z;
}
double jvli(dian a, dian b) {int x abs(a.x - b.x);int y abs(a.y - b.y);int z abs(a.z - b.z);double q x * x y * y z * z;double p pow(q, 0.5);return p;
}
int main() {double sum 0;cin N;dian a[50005];for (int i 0; i N; i) {cin a[i].x a[i].y a[i].z;}sort(a, a N, cmp);for (int i 0; i N-1; i) {sum jvli(a[i], a[i 1]);}printf(%.3lf, sum);return 0;
}
P1104 生日
生日 - 洛谷
题目 解答
思路
创建 学生 结构体记录编号根据输入顺序进行编号姓名出生年、月、日依据题目要求对学生结构体数组中的每个元素排序
代码
#includeiostream
#includestring
#includealgorithm
using namespace std;
int n;
typedef struct student {int num;string name;int y;int m;int d;
}student;
bool cmp(student a, student b) {if (a.y ! b.y)return a.y b.y;else {if (a.m ! b.m)return a.m b.m;else {if (a.d ! b.d)return a.d b.d;elsereturn a.num b.num;}}
}
int main() {cin n;student s[105];for (int i 0; i n; i) {cin s[i].name s[i].y s[i].m s[i].d;s[i].num i;}sort(s, s n, cmp);for (int i 0; i n; i) {cout s[i].name endl;}return 0;
}
P1012 拼数
[NOIP1998 提高组] 拼数 - 洛谷
题目 解答
思路
若要得到最大的整数则需要 0~9 中的大数做高位故而不是比较 ai 的大小而是将 ai 作为字符串比较字典序
现有 A 和 B要使二者拼接后最大则应该比较 AB 与 BA 的大小据此对这 n 个整数进行排序然后依次输出即为 拼接后最大的整数
代码
#includeiostream
#includestring
#includealgorithm
using namespace std;
string s[25];
int n;
bool cmp(string a, string b) {return (a b) (b a);
}
int main() {cin n;for (int i 0; i n; i)cin s[i];sort(s, s n, cmp);for (int i 0; i n; i)cout s[i];return 0;
}
