3641. 整数划分

tyuiop

我竟然蠢到被溢出卡

gqxing

这段程序为什么为什么通不过第五个测试啊

include

include

using namespace std;
int divide(int n,int ans[]) {
int sum = (1 + n)n / 2;
if (sum % 3 != 0)
return 0;
int as = sum / 3;
list l;
for (int i = n; i >= 1; i–)
l.push_back(i);
int index = 3;
while (l.size()> 0) {
list::iterator it = l.begin();
list::iterator end = l.end();
int temp = 0;
list la;
while ( it != end ) {
if (temp + (
it) > as)
it++;
else if (temp + (it) < as) {
temp += (
it);
la.insert(la.begin(), it);
it=l.erase(it);
}
else {
la.insert(la.begin(),
it);
l.erase(it);
break;
}
}

    for (list<int>::iterator oli = la.begin(); oli != la.end(); oli++) {
        ans[*(oli)] = index;
    }
    index--;
    la.clear();
}
return 1;

}
int main()
{
int a[200000] = { 0 };
int n;
cin >> n;
int ret=divide(n,a);
int i = 1;
if (ret = 0) {
cout << “Impossible” << endl;
}
else {
while (a[i] != 0) {
cout << a[i] << ” “;
i++;
}
cout << endl;
}
return 0;
}

ChengChao

n<=3时无解,由于n==6的时候可以有123321的解法,那么可以用n%6的结果进行枚举出每一个结果。n%6可能的结果为0,1,2,3,4,5.其中由于摸为1和4试不能等分为三份,故考虑摸为0,2,3,5时即可。对于摸为2,3,5时先处理前8,9,5个元素。

你当前正在回复 博客/题目
存在问题!