Codeforces 872C(贪心)

Codeforces 872C
考虑因为最小的合数是$4$,所以分$4$最优
如果$n$除以$4$有余数,那么由余数讨论:
$0$: 直接输出$n / 4$
$1$: 4 4 1可以组成合数$9$当且仅当$n / 4 \geq 2$,输出$n / 4 - 1$
$2$: 4 2可以组成合数$6$当且仅当$n / 4 \geq 1$,输出$n / 4$
$3$: 4 4 4 3可以组成合数$15$当且仅当$n / 4 \geq 3$,输出$n / 4 - 1$
如果一个也不符合则输出$-1$

以上组合是最小包含余数和$4$的组合,所以这样是最优的

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
//cf only
#define LD "%I64d"
#define D "%d"
#define pr printf
#define sc scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
using namespace std;
int read() {int x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
int Q, n;
void clean() {
}
void solve() {
clean();
while (Q--) {
scanf("%d", &n);
int yyqaknoi = n / 4, wylaknoi = n % 4;
int flag = false;
switch (wylaknoi) {
case 0 : {printf("%d\n", yyqaknoi); flag = 1;} break;
case 1 : if (yyqaknoi >= 2) {printf("%d\n", yyqaknoi - 1); flag = 1; } break;
case 2 : if (yyqaknoi >= 1) {printf("%d\n", yyqaknoi); flag = 1;} break;
case 3 : if (yyqaknoi >= 3) {printf("%d\n", yyqaknoi - 1); flag = 1;} break;
}
if (!flag) printf("-1\n");
}
}
int main() {
scanf("%d", &Q), solve();
return 0;
}

------ 本文结束 ------