パーフェクト数列(25)C++版
タイトル
ぶんせき
まず配列を大きくから小さく並べ替えると、より便利になります.次に2つのループを作成し、外ループは最小値を表し、内ループはM<=N*pの要求を満たす数を表し、1回を満たすたびにcnp(完璧な数列を構成する数を表す)の数が1増加する.次の内循環は(cnp+最小値i)から始まり(この時点で1つの満たす完璧な数の列の数がどれだけあるかを知っていることを示し、唯一の問題はcnpが1つの完璧な数の列の数を最大で満たすかどうかを確認することである)、M<=N*pを満たさなければ直接終了する;満たされている場合はcnpを更新し、cnpが最大であることを知っている.
コード#コード#
これは牛客網の中の大神を見たもので、自分で思いついたものではありません.
ぶんせき
まず配列を大きくから小さく並べ替えると、より便利になります.次に2つのループを作成し、外ループは最小値を表し、内ループはM<=N*pの要求を満たす数を表し、1回を満たすたびにcnp(完璧な数列を構成する数を表す)の数が1増加する.次の内循環は(cnp+最小値i)から始まり(この時点で1つの満たす完璧な数の列の数がどれだけあるかを知っていることを示し、唯一の問題はcnpが1つの完璧な数の列の数を最大で満たすかどうかを確認することである)、M<=N*pを満たさなければ直接終了する;満たされている場合はcnpを更新し、cnpが最大であることを知っている.
コード#コード#
これは牛客網の中の大神を見たもので、自分で思いついたものではありません.
#include
using namespace std;
const int maxn = 100005;
int a[maxn];
int main() {
freopen("datain.txt","r",stdin);
int n, p;
scanf("%d %d", &n, &p);
for (int i = 0; i < n; i++) {
scanf("%d",&a[i]);
}
sort(a,a+n);
int maxNum = a[n-1];
int cnp = 0;
for (int i = 0; i < n; i++) {
for (int j = i+cnp; j < n; j++) {
if (a[j] > a[i]*p) break;
cnp++;
}
}
//for (int i = 0; i < n; i++) {
// printf("%d ",a[i]);
//}
printf("%d
", cnp);
return 0;
}