链式投票|流向贪心

lc

lc797

先凑总和非负，找唯一负数位置

从近到远取两边正数补负数，累计移动步数得最小操作数

class Solution {
public:
long long minMoves(vector<int>& balance) {
long long total = 0;
int neg_idx = -1;
for (int i = 0; i < balance.size(); i++) {
int x = balance[i];
total += x;
if (x < 0) {
neg_idx = i;
}
}

if (total < 0) { // 总和必须非负
return -1;
}
if (neg_idx < 0) { // 没有负数，无需操作
return 0;
}

int n = balance.size();
int need = -balance[neg_idx];
long long ans = 0;
for (int dis = 1; ; dis++) { // 把与 neg_idx 相距 dis 的数移到 neg_idx
int s = balance[(neg_idx - dis + n) % n] + balance[(neg_idx + dis) % n];
if (s >= need) {
ans += 1LL * need * dis; // need 个 1 移动 dis 次
return ans;
}
ans += 1LL * s * dis; // s 个 1 移动 dis 次
need -= s;
}
}
};

lc277

1.找候选人

2.check候选人(3种situation)

/* The knows API is defined for you.
bool knows(int a, int b); */

class Solution
{
public:
int findCelebrity(int n)
{
int candidate = 0; //候选人
for (int x = 1; x < n; x ++)
{
if ( knows(candidate, x) == true ) //若候选人认识别人，就不可能是名人。名人不认识其他人
{
candidate = x; //所有人，一定认识名人
//////小于x的那些，要么是因为 (1)被人不知，if被人知，就抢到了candidate了
//////（2） 要么是因为认识了别人，就放弃了candidate
}
}

for (int x = 0 ; x < n; x ++)
{
if (candidate == x) //名人不认识其他人，但是认识自己
continue;
if ( knows(candidate, x) == true)
return -1; //名人不应该认识 anyone
if (knows(x, candidate) == false)
return -1; //anyone 认识名人
}

return candidate;
}
};