废话不多说,先上思路
一开始的思路是贪心,就是先尽量取4,取不了了再去取3
我们可以得到以下规律:
9 = 4 4; 10 = 4 4;
11 = 4 4; 12 = 4 4 4;
等等!好像有点不对!!
9 = 3 3 3; 10 = 3 3 4;
11 = 3 4 4; 12 = 4 4 4;
看上去有模有样的!
请问12这个数到底是作为3个4分割还是4个3分割好呢?
由图可得,12作为3分割更好
那么结论已经显而易见了:
由此得到我们的代码
#include <iostream>
using namespace std;
int a[20];//注意这里:数组开long long通过率80%
long long cnt = 0;
int main() {
for (int i = 1; i <= 8; i++)
cin >> a[i];
for (int i = 1; i <= 8; i++) {
a[i + 1] += a[i] / 3;//*式
if (a[i] >= 3){
if(a[i]==5)cnt+=4*i;
else cnt += a[i] * i;
}
}
cout << cnt;
return 0;
}
剩下的20%为什么会WA了呢?
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
ll a[20];
ll cnt = 0;
int main() {
for (int i = 1; i <= 8; i++)
cin >> a[i];
for (int i = 1; i <= 8; i++) {
if (a[i] >= 3){
if(a[i]==5)cnt+=4*i;
else cnt += a[i] * i;
a[i + 1] += a[i] / 3;//12行的*式被换到了这里
}
}
cout << cnt;
return 0;
}