3月15日蚂蚁研发岗真题解析

四季读书网 2026-03-15 14:05:35 3 0

3月15日蚂蚁研发岗真题解析

🔗刷题网址: bishipass.com

蚂蚁-2026.03.15-研发岗

题目一：房屋骨架搭建

这题的关键不是模拟拼房子，而是先看一根房子骨架到底需要几对等长木棍。把问题化成“总共能不能凑出至少 3 对”之后，判断就变得非常直接。容易卡壳的点在于三角形是否合法，其实只要从三对里合理分配，条件天然满足。

难度：简单

题目二：翻转数组后的好二元组最大值

题面操作很多，但位置最终只会在和之间二选一，所以核心是统计有多少位置能落到“小于等于 ”这一侧。把可行的区间推出来以后，答案就是最大化。真正容易错的是上下界分类，尤其是哪些点“可选”、哪些点“必选”。

难度：中等

题目三：幂次加法下的最少追平次数

把两数追平，等价于用最少个带符号的二进制幂表示差值，这就是 NAF 的经典模型。题目表面像搜索，实际上每次只需要根据奇偶和模 4 情况贪心缩小差值。这里最值得记住的不是公式本身，而是为什么可以写成，从而比普通二进制拆分更优。

难度：中等偏难

1. 房屋骨架搭建

问题描述

K 小姐手里有一批木棍，想搭出一个“房子”形状：

>
下半部分是一个长方形；
>
上半部分是一个等腰三角形；
>
长方形的上边同时也是三角形的底边。

每根木棍长度都是正整数，并且每根木棍最多使用一次。

请你判断，是否能从这些木棍中挑出若干根，恰好拼出这样的房子。

输入格式

第一行输入一个整数，表示木棍数量。

第二行输入个整数，表示每根木棍的长度。

输出格式

如果能够拼出这样的房子，输出 YES；否则输出 NO。

样例输入 1

64 4 3 3 5 5

样例输出 1

YES

样例输入 2

64 4 3 3 2 1

样例输出 2

NO

数据范围

题解

先把房子的边数想清楚。

这个图形虽然看起来像“长方形 + 三角形”，但由于两部分共用了一条边，所以真正需要的边是：

>
长方形的上下边各一根；
>
长方形的左右边各一根；
>
屋顶的两条腰各一根。

总共需要根木棍，也就是 3 对等长木棍。

于是问题就变得非常直接了：

统计所有长度能提供的“成对木棍”数量之和，看看是否至少有对。

设某个长度出现了次，那么它最多能提供：

对木棍。

把所有长度贡献的对数加起来：

只要这个值不小于，答案就是 YES。

#为什么这样就够了

因为只要已经拿到了对木棍：

>
一对做宽；
>
一对做高；
>
一对做屋顶两条腰。

而三角形底边就是“宽”对应的那一对中的上边。

如果担心等腰三角形是否合法，只要把三对里最短的一对拿来做底边，另外任意一对做屋顶腰即可。因为屋顶腰长度是正整数，且不小于底边长度的一半，所以：

三角形一定能成立。

#复杂度分析

只需要统计每种长度出现了多少次。

时间复杂度是，空间复杂度是，其中是不同长度的数量。

参考代码

>
Python

import sysfrom collections import Counterinput = lambda: sys.stdin.readline().strip()defsolve() -> None:    n = int(input())    arr = list(map(int, input().split()))    cnt = Counter(arr)    pairs = 0for v in cnt.values():        pairs += v // 2    print("YES"if pairs >= 3else"NO")if __name__ == "__main__":    solve()

>
Cpp

#include<bits/stdc++.h>usingnamespacestd;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;unordered_map<int, int> cnt;for (int i = 0; i < n; ++i) {int x;cin >> x;        ++cnt[x];    }longlong pairs = 0;for (auto &[k, v] : cnt) {        pairs += v / 2;    }cout << (pairs >= 3 ? "YES" : "NO") << '\n';return0;}

>
Java

import java.io.BufferedInputStream;import java.io.IOException;import java.io.InputStream;import java.util.HashMap;import java.util.Map;publicclassMain{publicstaticvoidmain(String[] args)throws Exception {        FastScanner fs = new FastScanner(System.in);int n = fs.nextInt();        Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < n; i++) {int x = fs.nextInt();            cnt.put(x, cnt.getOrDefault(x, 0) + 1);        }long pairs = 0;for (int v : cnt.values()) {            pairs += v / 2;        }        System.out.println(pairs >= 3 ? "YES" : "NO");    }staticclassFastScanner{privatefinal InputStream in;privatefinalbyte[] buf = newbyte[1 << 16];privateint ptr = 0;privateint len = 0;        FastScanner(InputStream is) {            in = new BufferedInputStream(is);        }privateintread()throws IOException {if (ptr >= len) {                len = in.read(buf);                ptr = 0;if (len <= 0) {return -1;                }            }return buf[ptr++];        }intnextInt()throws IOException {int c;do {                c = read();            } while (c <= ' ' && c != -1);int sign = 1;if (c == '-') {                sign = -1;                c = read();            }int val = 0;while (c > ' ') {                val = val * 10 + c - '0';                c = read();            }return val * sign;        }    }}

2. 翻转数组后的好二元组最大值

问题描述

给定一个长度为的数组，初始时满足：

定义一个有序对为“好的二元组”，当且仅当：

>
；
>
；
>
；
>
。

你可以进行任意次操作。每次操作选择一个下标，把它的值改成：

请计算，在最优操作后，数组中最多能有多少个不同的好的二元组。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个整数，表示测试数据组数。

接下来每组数据输入两个整数。

输出格式

对于每组测试数据，输出一个整数，表示最多能得到多少个好的二元组。

样例输入

45 24 11 13 10

样例输出

数据范围

题解

这题看起来像是在改数组，实际上真正重要的只有一件事：

最终有多少个位置满足。

设这个数量是，那么剩下满足的位置数就是。

由于好二元组是有序对，前一个位置来自“小的一侧”，后一个位置来自“大的一侧”，所以答案就是：

于是问题就转化成：** 最多能取哪些值。**

#每个位置能取到什么值

初始时第个位置是。

操作一次之后，它会变成：

所以位置最终只能在这两个值里二选一：

#哪些位置能够变成“小于等于 ”

一个位置能成为“小的一侧”，等价于它的两个候选值里至少有一个不大于。

于是满足条件当且仅当：

因此，最终可以放进“小的一侧”的位置总数上界是：

#哪些位置必定属于“小的一侧”

如果位置的两个候选值都不大于，那它无论怎么翻转都只能算进小的一侧。

这要求同时满足：

也就是：

这样的点数为：

所以，的可取范围就是：

如果原本，那么所有值都不大于，答案显然就是。

#最后怎么取最优

函数：

是一个开口向下的抛物线，在最接近的地方取到最大值。

所以只需要把取成可行区间里最靠近的整数即可。

#复杂度分析

每组数据只需要做常数次计算。

时间复杂度是，空间复杂度是。

参考代码

>
Python

import sysinput = lambda: sys.stdin.readline().strip()defbest_value(n: int, m: int) -> int:    m = min(m, n)if m == n:return0    low = max(0, 2 * m - n)    high = min(n, 2 * m)    mid = n // 2    ans = 0for x in (low, high, max(low, min(high, mid)), max(low, min(high, mid + 1))):        ans = max(ans, x * (n - x))return ansdefsolve() -> None:    t = int(input())    out = []for _ in range(t):        n, m = map(int, input().split())        out.append(str(best_value(n, m)))    sys.stdout.write("\n".join(out))if __name__ == "__main__":    solve()

>
Cpp

#include<bits/stdc++.h>usingnamespacestd;longlongbestValue(longlong n, longlong m){    m = min(m, n);if (m == n) {return0;    }longlong low = max(0LL, 2LL * m - n);longlong high = min(n, 2LL * m);longlong mid = n / 2;longlong ans = 0;vector<longlong> cand = {low, high, max(low, min(high, mid)), max(low, min(high, mid + 1))};for (longlong x : cand) {        ans = max(ans, x * (n - x));    }return ans;}intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {longlong n, m;cin >> n >> m;cout << bestValue(n, m) << '\n';    }return0;}

>
Java

import java.io.BufferedInputStream;import java.io.IOException;import java.io.InputStream;publicclassMain{staticlongbestValue(long n, long m){        m = Math.min(m, n);if (m == n) {return0;        }long low = Math.max(0L, 2L * m - n);long high = Math.min(n, 2L * m);long mid = n / 2;long ans = 0;long[] cand = newlong[]{low, high, clamp(mid, low, high), clamp(mid + 1, low, high)};for (long x : cand) {            ans = Math.max(ans, x * (n - x));        }return ans;    }staticlongclamp(long x, long l, long r){return Math.max(l, Math.min(r, x));    }publicstaticvoidmain(String[] args)throws Exception {        FastScanner fs = new FastScanner(System.in);int t = fs.nextInt();        StringBuilder sb = new StringBuilder();for (int cs = 0; cs < t; cs++) {long n = fs.nextLong();long m = fs.nextLong();            sb.append(bestValue(n, m)).append('\n');        }        System.out.print(sb);    }staticclassFastScanner{privatefinal InputStream in;privatefinalbyte[] buf = newbyte[1 << 16];privateint ptr = 0;privateint len = 0;        FastScanner(InputStream is) {            in = new BufferedInputStream(is);        }privateintread()throws IOException {if (ptr >= len) {                len = in.read(buf);                ptr = 0;if (len <= 0) {return -1;                }            }return buf[ptr++];        }longnextLong()throws IOException {int c;do {                c = read();            } while (c <= ' ' && c != -1);int sign = 1;if (c == '-') {                sign = -1;                c = read();            }long val = 0;while (c > ' ') {                val = val * 10 + c - '0';                c = read();            }return val * sign;        }intnextInt()throws IOException {return (int) nextLong();        }    }}

3. 幂次加法下的最少追平次数

问题描述

给定两个整数。

你可以进行若干次操作，使它们最终相等。每次操作可以：

>
任选一个非负整数；
>
再从和中选择一个；
>
把被选中的那个数加上。

请计算，使与相等所需的最少操作次数。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个整数，表示数据组数。

接下来每组数据输入两个整数。

输出格式

对于每组测试数据，输出一个整数，表示最少操作次数。

样例输入

50 07 05 14-3 5-10 10

样例输出

数据范围

题解

这题真正影响答案的只有差值。

设：

如果最终两数能变相等，那么本质上就是要用若干个形如的数，把差值抵消掉。

为什么会出现正负号？

>
给较小的那个数加上，等价于“差值减少了 ”；
>
给较大的那个数加上，等价于“差值增加了 ”。

所以问题等价于：

用最少个带符号的二进制幂表示整数。

这正是 NAF（Non-Adjacent Form，非相邻表示） 的经典结论。

#状态转移怎么理解

记答案函数为。

1. 如果是偶数

那么最低位一定是，可以直接右移一位：

2. 如果是奇数

这时最低位一定要消掉一次，所以一定会贡献一次操作。

接下来有两种选择：

>
先减去，再整体除以；
>
先加上，再整体除以。

也就是：

#贪心怎么写

对于奇数：

>
如果，显然只要一次。
>
如果，优先走。
>
如果，优先走。

这就是 NAF 的贪心写法。

例如差值：

>
普通二进制拆分是，需要次；
>
NAF 写法是，只需要次。

#复杂度分析

每一步都会把当前差值至少缩小到一半量级。

所以单组复杂度是，空间复杂度是。

参考代码

>
Python

import sysinput = lambda: sys.stdin.readline().strip()defcalc(d: int) -> int:    d = abs(d)    ans = 0while d:if d & 1 == 0:            d >>= 1else:            ans += 1if d == 1or d & 3 == 1:                d = (d - 1) >> 1else:                d = (d + 1) >> 1return ansdefsolve() -> None:    t = int(input())    out = []for _ in range(t):        x, y = map(int, input().split())        out.append(str(calc(x - y)))    sys.stdout.write("\n".join(out))if __name__ == "__main__":    solve()

>
Cpp

#include<bits/stdc++.h>usingnamespacestd;longlongcalc(longlong d){    d = llabs(d);longlong ans = 0;while (d > 0) {if ((d & 1LL) == 0) {            d >>= 1;        } else {            ++ans;if (d == 1 || (d & 3LL) == 1) {                d = (d - 1) >> 1;            } else {                d = (d + 1) >> 1;            }        }    }return ans;}intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {longlong x, y;cin >> x >> y;cout << calc(x - y) << '\n';    }return0;}

>
Java

import java.io.BufferedInputStream;import java.io.IOException;import java.io.InputStream;publicclassMain{staticlongcalc(long d){        d = Math.abs(d);long ans = 0;while (d > 0) {if ((d & 1L) == 0) {                d >>= 1;            } else {                ans++;if (d == 1 || (d & 3L) == 1) {                    d = (d - 1) >> 1;                } else {                    d = (d + 1) >> 1;                }            }        }return ans;    }publicstaticvoidmain(String[] args)throws Exception {        FastScanner fs = new FastScanner(System.in);int t = fs.nextInt();        StringBuilder sb = new StringBuilder();for (int cs = 0; cs < t; cs++) {long x = fs.nextLong();long y = fs.nextLong();            sb.append(calc(x - y)).append('\n');        }        System.out.print(sb);    }staticclassFastScanner{privatefinal InputStream in;privatefinalbyte[] buf = newbyte[1 << 16];privateint ptr = 0;privateint len = 0;        FastScanner(InputStream is) {            in = new BufferedInputStream(is);        }privateintread()throws IOException {if (ptr >= len) {                len = in.read(buf);                ptr = 0;if (len <= 0) {return -1;                }            }return buf[ptr++];        }longnextLong()throws IOException {int c;do {                c = read();            } while (c <= ' ' && c != -1);int sign = 1;if (c == '-') {                sign = -1;                c = read();            }long val = 0;while (c > ' ') {                val = val * 10 + c - '0';                c = read();            }return val * sign;        }intnextInt()throws IOException {return (int) nextLong();        }    }}