最近小艺酱渐渐变成了一个圆滑的形状-球!! 小艺酱开始变得喜欢上球! 小艺酱得到n个同心圆。 小艺酱对着n个同心圆进行染色。 相邻的圆范围内不能有相同的颜色。相隔一层的圆颜色相同。 小艺酱想知道圆最外层的那种颜色全部染了多少?
按半径从大到小排列后, 一共有
1
∼
n
1 \sim n
1∼n层,
1
+
2
×
k
,
(
k
>
=
0
)
1 + 2 \times k, (k >= 0)
1+2×k,(k>=0)层颜色都相同,枚举并计算每一对相邻的有着不同颜色的同心圆的圆环面积
S
S
S,枚举过程中累计答案即可。注意
π
=
a
r
c
c
o
s
(
−
1
)
\pi=arccos(-1)
π=arccos(−1),在C++中等价于
π
=
a
c
o
s
(
−
1
)
\pi=acos(-1)
π=acos(−1),且需要引入cmath
头文件。
#include
#include
#include
#include
using namespace std;
const double PI = acos(-1);
const int N = 1010;
int n;
int r[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> r[i];
sort(r, r + n, greater<int>());
double res = 0;
for(int i = 0; i < n; i += 2)
res += (PI * r[i] * r[i] - PI * r[i + 1] * r[i + 1]);
printf("%.3lf\n", res);
return 0;
}
存在n个节点,目标节点在m。 每个节点有自己的权值a。 在权值k内(含k值)选择一个权值非0节点且与目标节点距离最近。 节点i与节点j的距离为abs(i-j)。
按题意向目标节点的两边进行枚举即可,注意权值不大于 k k k的同时,还要权值非 0 0 0。
#include
#include
#include
using namespace std;
const int N = 110;
int n, m, k;
int v[N];
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++) cin >> v[i];
int res1 = 0, res2 = n;
bool flag1 = false, flag2 = false;
for(int i = m + 1; i <= n; i ++) // 向右边枚举答案
{
if(v[i] && v[i] <= k)
{
flag1 = true;
res1 = i - m;
break;
}
}
for(int i = m - 1; i >= 1; i --) // 向左边枚举答案
{
if(v[i] && v[i] <= k)
{
flag2 = true;
res2 = m - i;
break;
}
}
if(flag1 && flag2) cout << min(res1, res2) << endl;
else if(flag1) cout << res1 << endl;
else cout << res2 << endl;
return 0;
}
已知存在n个宝物,每个宝物都有自己的质量m和价值v,在考虑选择宝物时只能选择总质量小于等于M的方案,请问在最
优方案下选择宝物,能获取到最大价值V是多少?
动态规划入门题,不懂的朋友可以查看csdn上的详解讲解。
#include
#include
#include
using namespace std;
const int N = 110, M = 1010;
int n, m;
int w[N], v[N];
int f[N][M];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i] >> v[i];
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= m; j ++)
{
if(j >= w[i])
{
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
}
else f[i][j] = f[i - 1][j];
}
cout << f[n][m] << endl;
return 0;
}
有N个客人与足够多张的圆桌。主人安排每位客人坐在一个圆桌边,但是每位客人希望自己左右边上分别有一些空座位,不然会觉得害羞。注意,如果一个客人所在的圆桌只有他一个人,那么他左边的空座位数量就是他右边的空座位数量。 试问主人需要准备多少个座位,才能让每个客人舒适的坐下。
抽象成一个无限大圆上有若干个点,每个点的两侧的虚拟点(以单位距离扩张)需要满足一定的限制,具体是当前点的右边的虚拟点数 R [ i ] R[i] R[i]要满足某一个点的左边虚拟点数 L [ j ] L[j] L[j]最接近即可,于是我们将 L 、 R L、R L、R排序,对于每一个相交的圆弧,我们需要将他们间的虚拟点数尽可能多的被同时用到,于是就可以取 c n t = m a x ( L [ i ] , R [ i ] ) cnt = max(L[i], R[i]) cnt=max(L[i],R[i])作为最大被用到的虚拟点数(每个点数被用到的次数只有两种情况:1和2),那么相当于是空座椅的个数加上 c n t cnt cnt,由于每个人也需要占用一个空座椅,最后的答案还需要加上人的个数 n n n,数据范围为 1 e 5 × 1 e 9 1e5 \times 1e9 1e5×1e9,会爆 i n t int int,答案需要用 l o n g l o n g long \ long long long存储。
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 10010;
int n;
int L[N], R[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> L[i] >> R[i];
sort(L + 1, L + 1 + n);
sort(R + 1, R + 1 + n);
LL res = n;
for(int i = 1; i <= n; i ++) res += max(L[i], R[i]);
cout << res << endl;
return 0;
}