Input
Output
Sample Input
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191
Sample Output
4 8
38 207
解题思路：这个题想明白一点就好写了。即蚂蚁的速度是一样的，转身不消耗时间，那么可以将两只相遇时掉头的蚂蚁，看做交错而过，不理会相遇即可。因为掉头与交错而过的时间是一样的。再暴力搜素每一个蚂蚁的位置，如果是最短时间，则比较
它距杆左边的距离与距杆右边的距离取最小，取出最大的最小值，即为所求 。如果是最长时间，比较它与杆左边的距离与杆右边的距离取最大，最后取出最大值。代码如下：
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <map> #include <stack> #include <utility> using namespace std; int const max_n=500; int a[max_n]; int main() { int m,n,t; scanf("%d",&t); while(t--){ cin>>m>>n; for(int i=0;i<n;i++)cin>>a[i]; int minN=0,maxN=0;//最短时间，最长时间 for(int i=0;i<n;i++)minN=max(minN,min(a[i],m-a[i])); for(int i=0;i<n;i++)maxN=max(maxN,max(a[i],m-a[i])); cout<<minN<<" "<<maxN<<endl; memset(a,0,sizeof(a)); } return 0; }
It is universally accknowledged that 泥煤(peat)是一个非常珍贵的收藏品，越大的泥煤收藏价值越高。
一天，王泥煤找到了阿拉伯神灯，也就是阿拉丁神灯的弟弟，他向阿拉伯神灯许了一个愿望，从此获得了一个超能力，可以将两个泥煤合并为更大的泥煤。但是这个能力非常的鸡肋，王泥煤需要支付与这两块泥煤等价值的财富才能将他们合并。
比如：王泥煤把两块价值分别为3和5的泥煤合并，可以得到一块价值为8的泥煤，但是要消耗3+5的财富。
王泥煤想知道，他将手中的n块泥煤合并到只剩下一块之后，最少需要花费多少财富。
Input
第一行为一个整数n（n <= 20000），代表王泥煤拥有的泥煤数量，接下来n行，每行一个整数a_i(1 <= a_i <= 50000)，代表每个泥煤的价值
Output
输出包括一行，请告诉王泥煤他需要花费的最少财富。
Sample Input
3
8
5
8
Sample Output
34
解题思路：就是不断选取最小的两块煤进行合成，合成后放入煤堆再找两个最小的，如果取一次排序一次，时间复杂度太高o（n^2），因此要用到优先队列 ，注意使用默认的greater 按升序排序就可以了。注意数据范围，要开long long 代码如下：
#include <iostream> #include <algorithm> #include <queue> #include <stack> #define LL long long using namespace std; int main() { int n,x; LL maxq=0; scanf("%d",&n); priority_queue<LL,vector<LL>,greater<LL> >q; for(int i=0;i<n;i++){scanf("%d",&x);q.push(x);} while(q.size()!=1) { LL a,b; a=q.top();q.pop(); b=q.top();q.pop(); LL c=a+b; q.push(c); maxq+=c; } cout<<maxq<<endl; return 0; }
Input输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
解题思路：因为不能漏掉任何一个导弹，所以要从第一个导弹开始，构建一个下降子序列；而在构建下降过程中的导弹若高于上一个导弹，则必须要使用新的拦截系统。这题我一开始写的挺复杂的，过了之后看题解，发现自己想复杂了，可以开一个数组，输入一个
导弹高度 ，若高于现在所有的拦截系统的高度，则必须新开一个拦截系统；若有拦截系统能够拦下它，则更新该拦截系统的高度。参考链接：https://blog.csdn.net/sdut_jk17_zhangming/article/details/79292887
代码如下：
#include<stdio.h> int main() { int a[300] = {0},i,n,j,h,m; while(scanf("%d",&n) != EOF) { m = 0; for(i= 0;i <n;i++) { scanf("%d",&h); for(j = 0;j <m;j++) { if(a[j] >= h) break; } if(j <m) a[j] = h; else { a[m] = h; m++; } } printf("%d\n",m); } return 0; }
写题的过程中，有不会的是很正常的，若是自己能写过，就坚持写完，写完找找题解，了解别人的思路再与自己的思路对比，最好能学到最优解。所有做题过程中不要太过于纠结题解问题，关键在于看了有没有学会最优解（或者说相对较好的思路）。
原文：https://www.cnblogs.com/whocarethat/p/11015649.html