思路
先设 \(f_{i,j}\) 表示到第 \(i\) 秒时，正在煎某一面，另一面煎了 \(j\) 分钟
我们就有转移：
\[f_{i,j}=f_{i-1,j} \]（不翻面的情况）
\[f_{i,j}=f_{i-1,i-j}+1 \]（翻面，而且在区间内）
这是 \(O(n^2)\) 的，不能过
我们发现，显然一个区间内最多翻转两次，因为三次或以上可以合并成一或两次更优
我们考虑整个区间进行转移，\(f_{i,j}\) 的 \(i\) 表示区间，\(j\) 不变
因此有转移：
不翻转：
\[f_{i,j} = f_{i-1,j} \]翻转一次，翻转后到 \(r_i\) 煎了 \(k\) 秒：
\[f_{i, j}=\min\{f_{i - 1, r - j - k}\}+1 \]翻转两次，两次之间煎了 \(k\) 秒：
\[f_{i,j}=\min\{f_{i - 1, j - k}\} + 2 \]但这仍是 \(n^2m\) 的
看到 \(\min\)，可以想到用单调队列进行转移
翻转一次的转移，弹出条件为 \(k>r-l\)，即 \(p<l-j\)
翻转两次的转移，弹出条件为 \(k>r-l\)，即 \(p<j+l-r\)
（这里的 \(p\) 即为转移点，注意翻转一次要用倒序）
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int reads()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
#define inf 1061109567
int n, m, l, r, i, f[2][200005];
std::deque<int> q;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = reads(), m = reads();
memset(f[0] + 1, 63, sizeof(int) * (n << 1));
while(m--)
{
l = reads(), r = reads(), i = i ^ 1, q.clear();
memcpy(f[i], f[i ^ 1], sizeof(int) * ((n << 1) + 1));
ROF(j, r, 0)
{
while(!q.empty() && f[i ^ 1][r - j] <= f[i ^ 1][q.back()]) q.pop_back();
while(!q.empty() && q.front() < l - j) q.pop_front();
q.push_back(r - j);
f[i][j] = std::min(f[i][j], f[i ^ 1][q.front()] + 1);
}
q.clear();
FOR(j, 0, r)
{
while(!q.empty() && f[i ^ 1][j] <= f[i ^ 1][q.back()]) q.pop_back();
while(!q.empty() && q.front() < j - r + l) q.pop_front();
q.push_back(j);
f[i][j] = std::min(f[i][j], f[i ^ 1][q.front()] + 2);
}
}
if(f[i][n] ^ inf) printf("Full\n%d", f[i][n]);
else puts("Hungry");
return 0;
}