A. 金币

一道简单的模拟题，思路见代码。

#include <iostream>
using namespace std;
int n,q,c,s;
//n是有多少天
//s是获得的金币总量
//c是每天能获得的金币数
//q表示往后数q天，获得的金币都是c个
int main()
{
cin>>n;
c=q=1; //第一天（往后的一天），获得1个金币
for(int i=1; i<=n; i++) //要发n天金币
{
s+=c; //累加
q--; //已经发了一天
if(q==0) //要更新数据
{
c++; //每天获得金币的数量+1
q=c; //根据题意，以后的c天都是c个金币，q就是c
}
}
cout<<s;
return 0;
}

B. 总统选举

简单排序即可，但要注意最大可能到100位数字，故要对字符串进行排序而不是数字。由于字符串的默认排序方法是字典序，不能直接用sort，而应该自定义sort的排序方式，先判断字符串长度。

当然，也可以不用sort，一遍循环找最大值即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
struct node
{
int num;
string w;
}a[5010];
bool cmp(node x,node y)
{
if(x.w.length()==y.w.length()) return x.w>y.w;
return x.w.length()>y.w.length();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>a[i].w,a[i].num=i;
sort(1+a,1+a+n,cmp);
cout<<a[1].num<<endl<<a[1].w;
return 0;
}

C. 最大矩形

分析：

这是一道单调栈的经典例题，建议重点掌握。

要想找到里面的最大的面积，一定会有这么一种情况，得出的矩形的高度一定为所包含的某一个高度一致的。所以我们可以对某一个柱子的高度为标准，尽量的向两头扩展，这样就可以找出以它高度为标准的，并包含它本身的最大矩形。然后对每一个柱子都做类似的工作，最后挑出里面最大的矩形。

单从上述所说，一定会有重复的工作，如何剔除重复工作呢？而且什么叫做尽量向两头扩展呢？

重复工作之后再说。先说什么叫尽量向两头扩展。

如：2 1 4

第一个：2，以2为高度为准，向左右两头扩展，它只能想右扩展，因为1比2低了，就不可能扩展到1了。宽度只有1。

第二个：1，以1为高度为准，向左右两头扩展，向左，因为2比1高可以扩展过去；向右，因为4也高于1所以扩展到4，这样以1为高度的矩形宽为3了；

第三个：4，以4为高度为准，向左右两头扩展，向左，因为4比1、2都高，显然不可以扩展过去，这样以4为高度的矩形宽为1了。

所以要将其扩展过去，必须高度不低于当前扩展点的高度。

所以如果我们从第一个开始计算到第n个，计算到 i 时，如果我们可以快速的找出左边第一个（这里第一的意思是离i最近）比 i 的高度小的，就可以完成了向左扩展的工作，而向右扩展，我们本来就是一直向右走，所以直接扩展。这时候就轮到单调栈出场了，即一直保持单调递增的栈。

思考刚才的例子：

2进栈，左边无比其小的元素，记录其最左扩展位置为1；

1准备进栈，因为其进栈就破坏了单调栈的性质（2>1），这时2要出栈，因为1<2也说明了2不可能向右扩展，出栈，计算以2为准的矩形 2*1，然后1才进栈。1进栈前，发现其前一个元素，既是当前的栈顶2，比1高，而且2的左扩展从位置1开始，所以1也有理由从2的左起始位置开始（注意：2比1高），所以2出栈后，1进栈，其左扩展应为2的左扩展位置1；

4准备进栈，因为4>1直接进栈，其左扩展位置只能为3了。

最后要清空栈：4退栈，以为是最右的了，这此时右扩展只能为3了。左右扩展都为3，即是其本身，矩形为4*1；记录其位置以备后需；

1退栈，最右扩展只能是上一个退栈的元素位置，因为其高度比1高（单调栈的性质），所以利用刚才记录的位置，1的左右扩展就为1，3了，矩形1*3；

具体操作：

建立一个单调递增栈，所有元素各进栈和出栈一次即可。每个元素出栈的时候更新最大的矩形面积。

设栈内的元素为一个二元组（x, y），x表示矩形的高度，y表示矩形的宽度。

如何压栈并更新呢？

① 如果当前元素比栈顶元素大或者栈为空，则直接压栈（x，1）；

② 如果当前元素小于等于栈顶元素，则退栈，直到 当前元素大于栈顶元素或者栈为空时，压栈。

③在退栈的过程中要进行最大面积和累积宽度的更新：

例：

若原始矩形高度分别为2,1,4,5,1,3,3

高度为2的元素进栈，当前栈为（2，1）

高度为1的元素准备进栈，但必须从栈顶开始删除高度大于或等于1的矩形，因为2已经不可能延续到当前矩形。删除（2，1）这个元素之后，更新最大矩形面积为2*1=2，然后把它的宽度1累加到当前高度为1的准备进栈的矩形，然后进栈，当前栈为（1，2）

高度为4的元素进栈，当前栈为（1，2） （4，1）

高度为5的元素进栈，当前栈为（1，2） （4，1） （5，1）

高度为1的元素准备进栈，删除（5，1）这个元素，更新最大矩形面积为51=5，把1累加到下一个元素，得到（4，2），删除（4，2），更新最大矩形面积为42=8，把2累加到下一个元素，得到（1，4），1*4=4<8，不必更新，删除（1，4），把4累加到当前准备进栈的元素然后进栈，当前栈为（1，5）

高度为3的元素进栈，当前栈为（1，5） （3，1）

高度为3的元素准备进栈，删除（3，1），不必更新，把1累加到当前准备进栈的元素然后进栈，当前栈为（1，5） （3，2）

把余下的元素逐个出栈，（3，2）出栈，不必更新，把2累加到下一个元素，当前栈为（1，7），（1，7）出栈，不必更新。栈空，结束。

最后的答案就是8。

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
​
struct Node
{
long long val;
long long len;
};
​
stack<Node> s;
​
int main()
{
long long temp,Max,n,i,m;
Node q;
cin>>n;
Max=0;
for(i=0; i<n; i++)
{
scanf("%d",&q.val);
q.len=1;
temp=0;
if(s.empty())
s.push(q);
else if(q.val<=(s.top()).val)
{
while(!s.empty()&&q.val<=(s.top().val))
{
(s.top()).len+=temp;
m=(s.top()).val*(s.top()).len;
if(m>Max) Max=m;
temp=(s.top()).len;
s.pop();
}
q.len+=temp;
s.push(q);
}
else
s.push(q);
}
temp=0;
while(!s.empty())
{
(s.top()).len+=temp;
m=(s.top()).val*(s.top()).len;
if(m>Max) Max=m;
temp=(s.top()).len;
s.pop();
}
cout<<Max<<endl;
return 0;
}

D. 雷达

思路：

知道小岛位置，和雷达半径，那么以小岛为圆心，雷达覆盖半径为半径画圆，可以求出小岛与x轴有0（雷达无法覆盖）、1（雷达只能在这个点上才能覆盖）、2个交点（雷达在两点之间都能覆盖该小岛）。如果有0个交点，直接输出-1；如果有1个交点，那么这个点必然安装雷达；如果有2个交点，则形成一条线段（也可以把一个点也看成无限短的线段以简化问题）。

要求最少雷达多少个，即把雷达放在1中线段的交集内。

那么这就变成了线段交集问题，即如果能放在几条线段的交集处，便贪心地尽量放在交集内，以减少使用的雷达数。（贪心）

如何实现？

以每个小岛为圆心做一个半径为d的圆，会与x轴相交与2点,leftEdge和rightEdge。可以知道所有安装在这个区间内的雷达均可以覆盖到该岛。以下简称小岛范围和小岛左右边界。

创建一个结构体数组记录以每个小岛左右边界，然后按照每个小岛的左边界将海岛进行升序排序。

定义leftEdge和rightEdge参数，用来记录当前最后一个雷达可以安装的范围。如果新加入的线段与雷达覆盖范围有交集，则不需要再加入新的雷达，如果没有交集则需装新雷达。由于小岛按照左边界排序，如果从左到右遍历，某个小岛范围已经不能与之前安装雷达有重叠，则后面的小岛也不会与之前安装雷达有重叠，所以每次只用记录最后一个新安雷达能安装的范围即可。

算法步骤：

先选左边界在最左边的岛，此时将雷达数量设为1，这个雷达可安装的位置为当前岛的左右边界之间。将leftEdge和rightEdge赋值。 double leftEdge = islands[0].leftEdge; double rightEdge = islands[0].rightEdge;

新加入一个岛，会出现两种情况： 

（1）如果该岛的islands[i].rightEdge<=rightEdge则不需加新雷达，只用修改当前最后一个雷达应该安装的范围即可，这个雷达应该安装在新的范围与之前雷达安装范围的交集中。更新当前最后一个雷达可安装位置 leftEdge = max(leftEdge, islands[i].leftEdge); rightEdge = min(rightEdge, islands[i].rightEdge) 

（2）如果该岛的islands[i].rightEdge>rightEdge则需加新雷达，这个雷达可安装范围应该与该小岛的范围相同。更新当前最后一个雷达可安装位置，并将雷达数量+1。 leftEdge = islands[i].leftEdge; rightEdge = islands[i].rightEdge;

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
​
struct island
{
double leftEdge;//记录在x轴上安装雷达可以辐射到岛时x最左边位置
double rightEdge;//记录在x轴上安装雷达可以辐射到岛的x最右边位置
island(double l = 0, double r = 0)
{
leftEdge = l;
rightEdge = r;
}
};
​
bool compare(island a, island b)
{
return(a.leftEdge < b.leftEdge);
}
​
int main()
{
int n, d;
cin >> n >> d;
island islands[1000];
int numofRadar = 0;//记录最小雷达数量
for (int i = 0; i < n; i++)
//输入雷达位置
{
int xPos, yPos;
cin >> xPos;
cin >> yPos;
if (yPos > d)numofRadar = -1;
double tmpLength = sqrt(abs((double)d * d - yPos * yPos));
islands[i].leftEdge = xPos - tmpLength;
islands[i].rightEdge = xPos + tmpLength;
}
sort(islands, islands + n, compare);
if (numofRadar != -1)
{
numofRadar = 1;
}
double leftEdge = islands[0].leftEdge;
double rightEdge = islands[0].rightEdge;
for (int i = 1; i < n; i++)
{
if (islands[i].leftEdge <= rightEdge)//两个范围有相交
{
//cout << "两个范围有相交"<<endl;
leftEdge = max(leftEdge, islands[i].leftEdge);
rightEdge = min(rightEdge, islands[i].rightEdge);
//此时雷达次数不需要增加，但是左右边界需要变化
}
else
//两个范围没有相交，需要重新加雷达
{
if (numofRadar != -1)
{
numofRadar++;//雷达数量++
}
leftEdge = islands[i].leftEdge;
rightEdge = islands[i].rightEdge;
}
}
cout<<numofRadar;
return 0;
}