这题能不能用循环来做?

0
0

从最后一张海报开始,数当前海报能撕掉的海报数量。

for(int i = n; i >= 1; --i){
    int cnt = 0;
    for(int j = i + 1; j <= n; ++j){
        if(海报i被覆盖){
            cnt = 0;
            break;
        }else if(海报i和海报j存在交集)){
            ++cnt;
        }
    }
    if(cnt >= ans){
        ans = cnt;
        idx = i;
    }
}

结果WA了,谁知道哪里错了

2 answer(s)

0

C覆盖了B,B覆盖了A,但C没有覆盖A,结果应该是撕A得到3张。而你的逻辑会得到2张

0

有的海报有可能被算了两次,例如,5 张海报,第 5 张覆盖第 4 张,第 5 张覆盖第 3 张,第 4 张覆盖第 3 张,这样就被算了两次

write answer 切换为英文 切换为中文


转发分享