# T1 模拟题

题目比较长就不描述了 ... 就是一道 字符串 模拟题

**通过 83.33%** (错误原因 : 字符串中可能存在 空格 需要用 getline(cin,s) 来读取字符串)

# T2 贪心 + 二分

## 题目描述
输入 : 5 个数 : $a,b,c,d,e$ , 数据范围 $[1,10^9]$ , 每次操作 取 其中 4 个数 减 一
输出 : **最多的操作次数**

## 解题思路

1. 首先将 $a,b,c,d,e$ 进行排序
2. 然后将 $c,d,e$ 都减去 $a$
3. 然后可以将 $b$ 给分配 $c,d,e$ 使得 $min(b,c,d,e)$ 最大 (可以 **二分求解** 最后的 $min(b,c,d,e)$)

**通过 100%**

## 代码参考 
```cpp
void solve() {
    for(int i = 0;i < 5;i ++) cin >> w[i];
    sort(w,w + 5);
    for(int i = 2;i < 5;i ++) w[i] -= w[0];
    int l = 0 , r = w[1];// w[1:4] 的最小值 的最大值 的范围
    while(l <= r) {
        int mid = (l + r) / 2;
        int d = w[1] - mid;
        for(int i = 2;i < 5;i ++) {
            if(w[i] < mid) d -= mid - w[i];
        }
        if(d < 0) r = mid - 1;
        else l = mid + 1;
    }
    cout<<w[0] + l - 1<<"\n";
}
```

# T3 背包题

## 题目描述

有 n 条直线 $A_i * X + B_i * Y = C_i$ , $1 \le n \le 10^4$ , $-10 \le A_i,B_i,C_i \le 10$ 且 $A_i , B_i \ne 0$ , **每条直线初始没有颜色。**

1. 你可以给每条直线上色 —— 黑色 或者 白色。
2. 你可以平移任意直线

输入 : n , 和 n 行数据 $A_i,B_i,C_i$

输出 : 黑白线的最多的交点(即 黑白点)个数

## 解题思路

1. 首先明确 :
   - 因为每一条直线都可以平移 , 所以 $C_i$ 没有作用
   - 两条平行的线之间无论如何都不会存在交点
   - 如果有 $x$ 条 黑线 , 那么任意一条与其都不平行的白线能产生的 交点个数为 $x$ 个。所以若 黑色的 有 $x$ 条 , 白色 的有 $y$ 条 , 且 黑色和白色的都不存在两条相互平行 , 那么此时能产生的最大的点的个数为 : $x * y$ 个
2. 所以 :
   - 首先我们按照 $\{A_i,B_i\}$ 的最简形式 $\{A_i',B_i'\}$ 来作为每一条直线的特征 , 平行的定义为同一条直线 , 用 $map<PII,int> mp$ 来存储
   - 然后用 $dp[i] = \{false , true\}$ 来表示 是否存在 最终黑色的线有 $i$ 条的方案
3. 最后 枚举 $1 \le s \le n$ , 如果 $dp[s] == true$ , 更新 $res = max(res,(n - s) * s)$

**通过 (93.33%) 14/15**

## 代码参考

```cpp
void solve() {
    cin >> n;
    map<PII,int> mp;
    for(int i = 0;i < n;i ++) {
        cin >> A[i] >> B[i] >> t;
        if(A[i] < 0) A[i] = -A[i] , B[i] = -B[i];
        t = gcd(A[i],B[i]); A[i] /= t , B[i] /= t;
        mp[{A[i],B[i]}] ++;
    }
    vector<int> h;
    for(auto& [k,v] : mp) h.push_back(v);
    vector<bool> dp(n + 1,false);
    dp[0] = true;
    for(auto& s : h) {
        for(int i = n;i >= s;i --) if(dp[i - s]) dp[i] = true;
    }
    int res = 0;
    for(int i = 1;i < n;i ++) if(dp[i]) res = max(res,(n - i) * i);
    cout<<res<<"\n";
}
```

求职面试

T1 模拟题
题目比较长就不描述了 ... 就是一道 字符串 模拟题
通过 83.33% (错误原因 : 字符串中可能存在 空格 需要用 getline(cin,s) 来读取字符串)
 T2 贪心 + 二分
 题目描述
输入 : 5 个数 : a,b,c,d,e , 数据范围 [1,10^9] , 每次操作 取 其中