acwing 4621.三个整数
原题链接:https://www.acwing.com/problem/content/4624/
解题思路
题目保证一定有解,说明给的abcd是一定可以找到答案xyz的
要求x + y > z
让左边取最大值,右边取最小值
即x取b,y取c,z取c
b + c > c恒成立(abcd都大于1已知)
代码
#include<iostream>
using namespace std;
int main()
{
int a,b,c,d;
cin >> a >> b >> c >> d;
cout << b << ' ' << c << ' ' << c ;
return 0;
}
acwing 4622.整数拆分
原题链接:https://www.acwing.com/problem/content/4625/
解题思路
f(x)表示除本身之外的最大因数 (x > 2)
哥德巴赫猜想:
任何一个大于等于6的偶数都可以表示成两个素数之和。
如果n为质数,不用拆分,结果为1
如果n为偶数:
如果n为偶合数:
n为4,结果为2
n >= 6,结果为2 (哥德巴赫猜想)
如果n为奇合数:(1 3 5 7 9,n一定大于等于9)
如果n-2为质数,就将n拆成(2,n-2),结果为2
如果n-2为合数,就将n拆成3和一个偶合数(不可能拆成两个质数,因为两个质数相加还是质数,所以拆出一个3剩下的一定是一个合数),可以拆成两个素数之和,结果为1 + 2 = 3
代码
#include<iostream>
using namespace std;
int n;
bool is_prime(int x)
{
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++)
{
if(x % i == 0) return false;
}
return true;
}
int main()
{
cin >> n;
if(is_prime(n)) puts("1");
else if(n % 2 == 0 || is_prime(n - 2)) puts("2");
else puts("3");
return 0;
}
acwing 4623.买糖果
原题链接:https://www.acwing.com/problem/content/4626/
解题思路
直接暴力模拟,会tle:如果存在每遍历一圈,至少有一个店铺就买不起了,那么时间复杂度可能会\(O(n^2)\),然而while暴力枚举可能情况会更糟,更tle
暴力枚举+优化:(每次计算出买一圈需要sum钱,买cnt个)
每次遍历一圈n个糖果店,这一次遍历可以计算花费了多少钱,买了多少个糖果
比如计算出来花费了sum钱,买了cnt个糖果。
那么这样的一圈,可以进行T/sum次(购买遍历),所以可以买T/sum * cnt个糖果,剩下的钱为T%sum。
如果某一圈中有一个糖果店中买不了了,那么在以后所有每次一圈一圈遍历,都是买不了的。
如果某次遍历了一圈,sum = 0,cnt = 0,说明就没有可以买的糖果店了。
关于时间复杂度:这样每次遍历一遍所有糖果店,计算出买一圈要钱sum,可以买cnt个糖果。每遍历一次出sum和cnt结果,都可以直接计算出可以进行T/sum次这样的过程,购买了T/sum * cnt个糖果,剩下T%sum元。那么最坏的情况就是每次有一个糖果店买不起了,看上去时间复杂度还是\(O(n^2)\),但是实际上,看 T %= sum: sum <= T(每次到T%sum时,恒成立)
1.若sum > T/2: T % sum = T-sum < T/2
2.若sum <= T/2: T%sum < sum <= T/2
因此每次T都会变成原来一般还小,所以总的时间复杂度大概是\(O(nlogn)\)
代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int a[N];
int n;
LL t,ans;
int main()
{
scanf("%d%lld",&n,&t);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
while(true)
{
LL sum = 0; // 一圈下来如果都取极限值就可能爆int
int cnt = 0;
for(int i = 1; i <= n;i ++)
{
if(sum + a[i] <= t) // 如果买得起就统计
{
sum += a[i];
cnt ++;
}
}
if(sum == 0) break;
ans += t/sum * cnt;
t %= sum;
}
printf("%lld\n",ans);
return 0;
}
标签:周赛,cnt,遍历,int,sum,71,一圈,acwing
From: https://www.cnblogs.com/rdisheng/p/16748820.html