我有这个问题:
你有问题。您已将第i个难度计算为整数ci。现在,您要使用已经遇到的一些问题为比赛准备一个问题集。
竞赛的问题集必须至少包含两个问题。您认为比赛问题的总难度必须至少为l,最大为r。此外,您认为最容易解决的问题和最难解决的问题之间的差异至少应为x。
查找为竞赛选择问题集的方法数量。
输入第一行包含四个整数n,l,r,x(1≤n≤15,1≤l≤r≤109,1≤x≤106)—您遇到的问题的数量,总和的最小值和最大值问题集的难度和包装中最困难的问题与最简单的问题之间的最小难度差异。
第二行包含n个整数c1,c2,...,cn(1≤ci≤106)-每个问题的难度。
输出打印为比赛选择合适的问题集的方法数量。
我试图解决它,但不幸的是我做不到。我请一个朋友给我一个主意,他为我解决了这个主意,但我不明白:
代码:
#include <stdio.h>
int a[25], l, r, x, i, j, n, ans;
int main(){
scanf("%d %d %d %d", &n, &l, &r, &x);
for(i=0; i<n; i++) scanf("%d", &a[i]);
for(i=0; i<(1<<n); i++){
int s = 0;
int max = 0, min = 1e9;
for(j=0; j<n; j++){
if((i>>j)&1){
if(a[j] > max) max = a[j];
if(min > a[j]) min = a[j];
s += a[j];
}
}
if(l <= s && s <= r && max-min >= x) ans++;
}
printf("%d", ans);
return 0;
}
他为什么要遍历那个数组直到i<(1<<n)
他只有n个元素?
为什么他这样做:if((i>>j)&1)
?
我知道这1<<n
等于乘以2的幂,并且1>>n
等于2除以n的整数除法,但这在这里是没有意义的。
您有n个可能的问题,并且每个问题都可以包含在问题集中或从中排除。这意味着每个问题都有2个选项,因此对于n个问题,有2 ^ n个选项可用于创建可能的问题集。
在这行中,for(i=0; i<(1<<n); i++)
您正在迭代所有这些可能的问题集,每个问题集都由0到2 ^ n-1之间的整数标识。接下来,我们需要确定哪些问题属于某个问题集,并且我们有代表它的整数。 。
为此,我们采用该整数的二进制表示形式。它具有n
位,并且可以说每个位对应一个问题:如果为1,则包含该问题,否则为不包含。这就是行if((i>>j)&1)
所执行的操作:它检查j
整数内部位置的位i
是否等于1,这意味着包括相应的问题。
其余的则更容易:从所有包含的问题中,计算出最小值,最大值和总和。然后,检查总和s
是否在有效范围内,最大和最小之间的差是否至少为x。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句