GreyOrange

01Roman Numerals in Strings

You are given a string that contains a name followed by Roman numerals. Your task is to return a vector of strings that stores:

1. The string name.
1. The numerical value of the Roman numeral (converted to integer). The names should be in ascending order, and if the names are the same, the numbers should also be sorted in ascending order. Input Format:
A list of strings where each string is in the format: name RomanNumeral. Output: Return a vector of strings, sorted by name and numeral value. Notes:
The Roman numeral, when converted to a number, is at most two digits.

Example 1

Input:

strings = ["John IX", "Mary XV", "John VIII", "Mary IX"]

Output:

["John 8", "John 9", "Mary 9", "Mary 15"]

Explanation: The names and their corresponding Roman numerals are sorted in ascending order. The Roman numerals are converted to integers as follows:

IX -> 9
XV -> 15
VIII -> 8
IX -> 9 The sorted output is: ["John 8", "John 9", "Mary 9", "Mary 15"].

解法

每条字符串以空格分割得到 (name, roman)，把 roman 转为 int(标准罗马规则)。按 (name, value) 二级排序后拼回 "name value"。时间 O(N log N · L)。

from typing import List

VAL = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

def roman_to_int(r: str) -> int:
    total = 0
    for i, c in enumerate(r):
        v = VAL[c]
        if i + 1 < len(r) and v < VAL[r[i + 1]]:
            total -= v
        else:
            total += v
    return total

def roman_in_strings(strings: List[str]) -> List[str]:
    pairs = []
    for s in strings:
        name, roman = s.rsplit(" ", 1)
        pairs.append((name, roman_to_int(roman)))
    pairs.sort()
    return [f"{n} {v}" for n, v in pairs]

import java.util.*;

class Solution {
    static int romanToInt(String r) {
        Map<Character, Integer> v = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
        int total = 0;
        for (int i = 0; i < r.length(); i++) {
            int cur = v.get(r.charAt(i));
            if (i + 1 < r.length() && cur < v.get(r.charAt(i + 1))) total -= cur; else total += cur;
        }
        return total;
    }
    public String[] romanInStrings(String[] strings) {
        String[][] pairs = new String[strings.length][2];
        Integer[] vals = new Integer[strings.length];
        for (int i = 0; i < strings.length; i++) {
            int idx = strings[i].lastIndexOf(' ');
            pairs[i][0] = strings[i].substring(0, idx);
            vals[i] = romanToInt(strings[i].substring(idx + 1));
        }
        Integer[] order = new Integer[strings.length];
        for (int i = 0; i < strings.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> { int c = pairs[a][0].compareTo(pairs[b][0]); return c != 0 ? c : vals[a] - vals[b]; });
        String[] out = new String[strings.length];
        for (int i = 0; i < strings.length; i++) out[i] = pairs[order[i]][0] + " " + vals[order[i]];
        return out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int romanToInt(const string& r) {
        unordered_map<char, int> v = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
        int total = 0;
        for (int i = 0; i < (int)r.size(); i++) {
            int cur = v[r[i]];
            if (i + 1 < (int)r.size() && cur < v[r[i+1]]) total -= cur; else total += cur;
        }
        return total;
    }
public:
    vector<string> romanInStrings(vector<string>& strings) {
        vector<pair<string, int>> p;
        for (auto& s : strings) {
            auto idx = s.rfind(' ');
            p.push_back({s.substr(0, idx), romanToInt(s.substr(idx + 1))});
        }
        sort(p.begin(), p.end());
        vector<string> out;
        for (auto& x : p) out.push_back(x.first + " " + to_string(x.second));
        return out;
    }
};

You are given an array of n elements and two variables, x and y. In each operation, you can: Subtract x from one element of the array. Subtract y from the remaining elements. Your task is to find the minimum number of operations required to make every element of the array ≤ 0. Input Format: The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the array. The third line contains two integers, x and y, where x > y. Output: Print the minimum number of operations to make each element ≤ 0.

Example 1

Input:

arr = [10, 20, 30, 40, 50]
x = 5
y = 2

Output:

Explanation: To make every element ≤ 0, the minimum number of operations required is 13.

解法

二分操作次数 m。一次操作每个元素至少减 y，被选中的那个再多减 x − y。共 m 次操作后元素 a_i 至少被减 m·y，最多再额外减 m·(x−y)(若每次都被选)。所以可行 iff 存在分配 c_i ≥ 0、∑ c_i = m，使 a_i − m·y − c_i·(x−y) ≤ 0，即 c_i ≥ max(0, a_i − m·y)/(x − y)。可行 iff ∑ ≤ m。二分上界用 max(a)/y + 1。时间 O(n log V)。

from typing import List

def array_operations(arr: List[int], x: int, y: int) -> int:
    def feasible(m: int) -> bool:
        need = 0
        for a in arr:
            rem = a - m * y
            if rem > 0:
                need += (rem + (x - y) - 1) // (x - y)
                if need > m:
                    return False
        return need <= m
    lo, hi = 0, max(arr) // y + 2
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

class Solution {
    public long arrayOperations(int[] arr, int x, int y) {
        long maxA = 0; for (int a : arr) maxA = Math.max(maxA, a);
        long lo = 0, hi = maxA / y + 2;
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (feasible(arr, x, y, mid)) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
    boolean feasible(int[] arr, int x, int y, long m) {
        long need = 0;
        for (int a : arr) {
            long rem = a - m * y;
            if (rem > 0) { need += (rem + (x - y) - 1) / (x - y); if (need > m) return false; }
        }
        return need <= m;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long arrayOperations(vector<int>& arr, int x, int y) {
        long long maxA = 0; for (int a : arr) maxA = max(maxA, (long long)a);
        long long lo = 0, hi = maxA / y + 2;
        auto feasible = [&](long long m) {
            long long need = 0;
            for (int a : arr) {
                long long rem = a - m * y;
                if (rem > 0) { need += (rem + (x - y) - 1) / (x - y); if (need > m) return false; }
            }
            return need <= m;
        };
        while (lo < hi) { long long mid = (lo + hi) / 2; if (feasible(mid)) hi = mid; else lo = mid + 1; }
        return lo;
    }
};

03Triangle and Points

You are given the coordinates of a triangle with three vertices:

(x1, y1)
(x2, y2)
(x3, y3) Additionally, you are provided the coordinates of two points:
Point p: (xp, yp)
Point q: (xq, yq) Your task is to determine the following:
Print '1' if the triangle cannot be formed.
Print '2' if both p and q lie inside the triangle.
Print '3' if only point p lies within the triangle.
Print '4' if only point q lies within the triangle.
Print '5' if neither point lies inside the triangle. Input Format:
Coordinates of the triangle vertices: x1, y1, x2, y2, x3, y3
Coordinates of the points p and q: p(xp, yp), q(xq, yq)

Example 1

Input:

x1 = 0
y1 = 0
x2 = 5
y2 = 0
x3 = 0
y3 = 5
xp = 1
yp = 1
xq = 6
yq = 6

Output:

Explanation: Only point p lies inside the triangle.

解法

用叉积判三角形是否退化(面积为 0 即 cannot be formed → 返回 1)。点在三角形内部用三个有向叉积同号(≥0)判定。组合 p、q 两点的判定得到 2/3/4/5。时间 O(1)。

def triangle_and_points(x1, y1, x2, y2, x3, y3, xp, yp, xq, yq) -> int:
    def cross(ax, ay, bx, by, cx, cy):
        return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
    area = cross(x1, y1, x2, y2, x3, y3)
    if area == 0:
        return 1
    def inside(px, py):
        d1 = cross(x1, y1, x2, y2, px, py)
        d2 = cross(x2, y2, x3, y3, px, py)
        d3 = cross(x3, y3, x1, y1, px, py)
        has_neg = d1 < 0 or d2 < 0 or d3 < 0
        has_pos = d1 > 0 or d2 > 0 or d3 > 0
        return not (has_neg and has_pos)
    p_in = inside(xp, yp)
    q_in = inside(xq, yq)
    if p_in and q_in: return 2
    if p_in: return 3
    if q_in: return 4
    return 5

class Solution {
    long cross(long ax, long ay, long bx, long by, long cx, long cy) {
        return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
    }
    boolean inside(long x1, long y1, long x2, long y2, long x3, long y3, long px, long py) {
        long d1 = cross(x1, y1, x2, y2, px, py);
        long d2 = cross(x2, y2, x3, y3, px, py);
        long d3 = cross(x3, y3, x1, y1, px, py);
        boolean neg = d1 < 0 || d2 < 0 || d3 < 0;
        boolean pos = d1 > 0 || d2 > 0 || d3 > 0;
        return !(neg && pos);
    }
    public int triangleAndPoints(int x1, int y1, int x2, int y2, int x3, int y3, int xp, int yp, int xq, int yq) {
        if (cross(x1, y1, x2, y2, x3, y3) == 0) return 1;
        boolean p = inside(x1, y1, x2, y2, x3, y3, xp, yp);
        boolean q = inside(x1, y1, x2, y2, x3, y3, xq, yq);
        if (p && q) return 2;
        if (p) return 3;
        if (q) return 4;
        return 5;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    long long cross(long long ax, long long ay, long long bx, long long by, long long cx, long long cy) {
        return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
    }
    bool inside(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3, long long px, long long py) {
        long long d1 = cross(x1, y1, x2, y2, px, py), d2 = cross(x2, y2, x3, y3, px, py), d3 = cross(x3, y3, x1, y1, px, py);
        bool neg = d1 < 0 || d2 < 0 || d3 < 0, pos = d1 > 0 || d2 > 0 || d3 > 0;
        return !(neg && pos);
    }
public:
    int triangleAndPoints(int x1, int y1, int x2, int y2, int x3, int y3, int xp, int yp, int xq, int yq) {
        if (cross(x1, y1, x2, y2, x3, y3) == 0) return 1;
        bool p = inside(x1, y1, x2, y2, x3, y3, xp, yp);
        bool q = inside(x1, y1, x2, y2, x3, y3, xq, yq);
        if (p && q) return 2;
        if (p) return 3;
        if (q) return 4;
        return 5;
    }
};

01Roman Numerals in Strings

Example 1

解法

02Array Operations

Example 1

解法

03Triangle and Points

Example 1

解法