Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

🍭 大家好这里是Kiyotaka-senpai , ein Programmierer, der Algorithmen liebt

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

✨ Diese Serie soll weiterhin aktualisiert werden Qiuzhao hat Testfragen geschrieben
👏 感谢大家的订阅➕ 和 喜欢💗

---

📧 清隆这边最近正在收集近一年半互联网笔试题汇总，有需要的小伙伴可以关注 Ende des Artikels Holen Sie sich die Prinzessinnen-Kreuzfahrt~

🎀 01.A先生的环形花圃

Beschreibung der Frage

Herr A hat ein rundes Blumenbeet, das in unterteilt ist $N$ Blockbereich. Zunächst wählte Herr A drei Bereiche im Blumenbeet aus, um Rosen zu pflanzen.

Nun möchte Herr A mit mobilen Einsätzen den Blumengarten erreichenAusgeglichener Zustand。

Ausgeglichener Zustand: Der Abstand zwischen zwei mit Rosen bepflanzten Flächen beträgt nicht weniger als $k$(Der Abstand zwischen benachbarten Bereichen beträgt $1$）。

Verschiebevorgang: Tauschen Sie den Status benachbarter Bereiche aus (Rosenbereich wird zu Leerbereich, leerer Bereich wird zu Rosenbereich).

Gleichzeitig legt Herr A großen Wert auf Effizienz und hofft daher, dass Sie mit möglichst wenigen Handgriffen das Blumenbeet in einen ausgeglichenen Zustand bringen können.

Eingabeformat

Geben Sie in der ersten Zeile eine positive Ganzzahl ein $T$, Angabe der Anzahl der Anfragen.

Nächste $T$ Zeilen, jede Zeile enthält fünf positive ganze Zahlen$N$、$k$、$A_1$、$A_2$、$A_3$, die jeweils die Anzahl der Beetbereiche, den erforderlichen Mindestabstand und die Ausgangsposition der drei Rosenbereiche darstellen.

Ausgabeformat

Ausgabe $T$ Zeilen, von denen jede eine Ganzzahl ausgibt, die die Mindestanzahl an Austauschvorgängen darstellt, die erforderlich sind, um das Blumenbeet ins Gleichgewicht zu bringen.Wenn das Gleichgewicht nicht erreicht werden kann, Ausgabe$-1$。

Beispieleingabe

3
5 1 1 2 3
5 2 1 2 3
6 2 2 3 6
1
2
3
4

Beispielausgabe

0
-1
1
1
2
3

Datenreichweite

$1\le T\le 10^4$
$1\le N\le 10^9$
$1\le k,A_1,A_2,A_3\le N$

Antwort

Dieses Problem kann durch die Analyse der Gleichgewichtsbedingungen gelöst werden.

Erstens, wenn der erforderliche Mindestabstand eingehalten wird $k$ Die Anzahl der Gartenflächen wurde überschritten$N$ Ein Drittel davon, dann kann die Bedingung nicht erfüllt werden, egal was passiert, und zu diesem Zeitpunkt die Ausgabe$-1$。

Ansonsten können wir zunächst die Positionen der drei Rosenbereiche sortieren und dann den Abstand zwischen benachbarten Rosenbereichen berechnen.Als nächstes für jeden Abstand, wenn dieser kleiner ist als$k$, dann ist eine Bewegungsoperation erforderlich und die Anzahl der Bewegungen beträgt $k$ Der Unterschied aus dieser Entfernung.

Wenn schließlich alle Abstände den Anforderungen entsprechen, erreicht das Blumenbeet einen ausgeglichenen Zustand und die Gesamtzahl der Bewegungen kann ausgegeben werden.

Die Zeitkomplexität ist $Ö(T\mathrm{sieheG}T)$, die Raumkomplexität ist $Ö(1)$。

Referenzcode

• Python

t = int(input())

for _ in range(t):
    n, k, *a = map(int, input().split())
    a.sort()

    if k * 3 > n:
        print(-1)
        continue

    b = [a[1] - a[0], a[2] - a[1], n - a[2] + a[0]]
    ans = sum(max(0, k - d) for d in b)

    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] a = new int[3];
            for (int i = 0; i < 3; i++) {
                a[i] = sc.nextInt();
            }

            Arrays.sort(a);

            if (k * 3 > n) {
                System.out.println(-1);
                continue;
            }

            int[] b = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
            int ans = 0;
            for (int d : b) {
                ans += Math.max(0, k - d);
            }

            System.out.println(ans);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• Cpp

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k, a[3];
        cin >> n >> k >> a[0] >> a[1] >> a[2];

        sort(a, a + 3);

        if (k * 3 > n) {
            cout << -1 << endl;
            continue;
        }

        int b[] = {a[1] - a[0], a[2] - a[1], n - a[2] + a[0]};
        int ans = 0;
        for (int d : b) {
            ans += max(0, k - d);
        }

        cout << ans << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

🪐 02.卢小姐的音游金币

Problembeschreibung

Frau Lu ist seit kurzem süchtig nach einem Musikspiel, bei dem Klavierklänge im Mittelpunkt stehen.Im Spiel hat jedes Klavierplättchen eine Zahl, wobei die Mindestzahl ist$1$ . Wenn Sie fünf Klavierplättchen mit steigenden Zahlen hintereinander treffen, erhalten Sie eine Goldmünze.

Zum Beispiel, wenn Miss Lu die Nummer drückt 1, 2, 3, 4, 5, 6 von Klavierstücken, dann für1, 2, 3, 4, 5 Für diese fünf Blöcke mit fortlaufend steigenden Zahlen erhält sie eine Goldmünze.

Wenn ein Level über einen längeren Zeitraum hinweg fortgeschritten ist, wird die Nummer zurückgesetzt. Die zurückgesetzte Nummer ändert sich von $1$ Start. Es ist also möglich, in einem Level mehrere Klavierplättchen mit der gleichen, aber unterschiedlichen Nummer zu treffen.

Beachten Sie, dass zum Erhalt von Goldmünzen nur fünf Klavierplättchen mit kontinuierlich steigenden Zahlen im gleichen Level erforderlich sind.

Aufgrund der überlegenen Stärke von Miss Lu hat sie vier Level bestanden.Miss Lu hat nun vier Schwierigkeitsstufen$A$、$B$、$C$ Und$D$ Anzahl der getroffenen Klavierplättchen. Wie viele Goldmünzen kann Frau Lu in diesen vier Leveln insgesamt erhalten?

Eingabeformat

Die erste Zeile enthält eine positive Ganzzahl $N$（$1\le N\le 10^5$), was die Gesamtzahl der von Miss Lu in den vier Levels getroffenen Klavierplättchen darstellt.

Nächste $N$ Geben Sie in jede Zeile drei Parameter ein:$A_{ichchchchchchchchchchchch}$、$B_{ichchchchchchchchchchchch}$（$1\le A_{ichchchchchchchchchchchch},B_{ichchchchchchchchchchchch}\le 10^9$)Und $C_{ichchchchchchchchchchchch}$（ ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i in {'A', 'B', 'C', 'D'}Cichchchchchchchchchchchch​∈{′A′,′B′,′C′,′D′}), die jeweils die Anzahl, Menge und Höhe jeder Klavierkachel darstellen.

Ausgabeformat

Geben Sie eine Ganzzahl aus, die die Gesamtzahl der Goldmünzen darstellt, die Frau Lu erhalten kann.

Beispieleingabe

11
1 1 A
2 2 A
3 2 A
4 2 A
5 2 A
6 1 A
7 1 B
8 2 B
9 2 B
10 2 B
11 1 B
1
2
3
4
5
6
7
8
9
10
11
12

Beispielausgabe

3
1

Beispielbeschreibung

Für Level $A$,Erste 1, 2, 3, 4, 5 Sie können eine Goldmünze bekommen und dann2, 3, 4, 5, 6 Sie können eine weitere Goldmünze erhalten.

Für Level $B$，7, 8, 9, 10, 11 Sie können eine Goldmünze erhalten.

Daher insgesamt $3$ Goldmünzen.

Beispieleingabe 2

5
1 1 C
2 2 C
3 2 C 
4 2 C
6 1 C
1
2
3
4
5
6

Beispielausgabe 2

0
1

Beispielbeschreibung 2

auf der Ebene $C$ Im Jahr können keine fünf aufeinanderfolgenden steigenden Zahlen ermittelt werden, daher beträgt die Anzahl der Goldmünzen$0$。

Datenreichweite

• $1\le N\le 10^5$
• $1\le A_{ichchchchchchchchchchchch},B_{ichchchchchchchchchchchch}\le 10^9$
• ci ∈ { ′ A ′ , ′ B ′ , ′ C ′ , ′ D ′ } c_i in {'A', 'B', 'C', 'D'}Cichchchchchchchchchchchch​∈{′A′,′B′,′C′,′D′}

Antwort

Dieses Problem kann mithilfe von Hashtabellen und Sortierung gelöst werden. Die konkreten Ideen sind wie folgt:

1. Verwenden Sie eine Hash-Tabelle cnt Notieren Sie, wie oft jede Zahl in jedem Level vorkommt. Der Schlüssel ist die Kombination aus Level-Zeichen und Zahl, und der Wert gibt an, wie oft die Zahl im Level vorkommt.

2. Sortieren Sie die Eingabedaten nach den Zeichen und Zahlen der Ebene, um sicherzustellen, dass die Zahlen derselben Ebene fortlaufend sind.

3. Durchlaufen Sie die sortierten Daten und bestimmen Sie für jede Zahl, ob alle fünf aufeinanderfolgenden Zahlen auf der aktuellen Ebene vorhanden sind. Wenn es existiert, nehmen Sie den Mindestwert der Häufigkeit des Vorkommens dieser fünf Zahlen, zählen Sie ihn in der Antwort und subtrahieren Sie den Mindestwert von der Häufigkeit des Vorkommens dieser fünf Zahlen.

4. Die endgültige Antwort ist die Summe aller Goldmünzen, die die Bedingungen erfüllen.

Die Zeitkomplexität ist $Ö(N\mathrm{sieheG}N)$, die Raumkomplexität ist $Ö(N)$。

Referenzcode

• Python

from collections import defaultdict
import sys

def solve():
    n = int(input())
    cnt = defaultdict(int)
    vec = []

    for _ in range(n):
        a, b, c = input().split()
        a, b = int(a), int(b)
        cnt[c + str(a)] += b
        vec.append((c, a))

    vec.sort()

    ans = 0
    for v in vec:
        arr = [v[0] + str(v[1] + i) for i in range(5)]
        t = min(cnt[a] for a in arr)
        ans += t
        for a in arr:
            cnt[a] -= t

    print(ans)

if __name__ == '__main__':
    solve()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Map<String, Integer> cnt = new HashMap<>();
        List<int[]> vec = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            String c = input[2];
            String key = c + a;
            cnt.put(key, cnt.getOrDefault(key, 0) + b);
            vec.add(new int[]{c.charAt(0), a});
        }

        vec.sort((x, y) -> {
            if (x[0] != y[0]) {
                return x[0] - y[0];
            }
            return x[1] - y[1];
        });

        long ans = 0;
        for (int[] v : vec) {
            String[] arr = new String[5];
            for (int i = 0; i < 5; i++) {
                arr[i] = (char) v[0] + String.valueOf(v[1] + i);
            }
            int t = Integer.MAX_VALUE;
            for (String a : arr) {
                t = Math.min(t, cnt.getOrDefault(a, 0));
            }
            ans += t;
            for (String a : arr) {
                cnt.put(a, cnt.get(a) - t);
            }
        }

        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

• Cpp

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    map<string, ll> cnt;
    vector<pair<string, int>> vec;

    for (int i = 1; i <= n; i++) {
        int a, b;
        string c;
        cin >> a >> b >> c;
        cnt[c + to_string(a)] += b;
        vec.push_back({c, a});
    }

    sort(vec.begin(), vec.end());

    ll ans = 0;
    for (auto& v : vec) {
        vector<string> arr;
        for (int i = 0; i < 5; i++) {
            arr.push_back(v.first + to_string(v.second + i));
        }
        ll t = LLONG_MAX;
        for (auto& a : arr) {
            t = min(t, cnt[a]);
        }
        ans += t;
        for (auto& a : arr) {
            cnt[a] -= t;
        }
    }

    cout << ans << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

✨ 03. Miss Lus einzigartiger Garten

Problembeschreibung

Miss Lu hat eine Länge von $N$ in einem bepflanzten Garten$N$ Pflanzen Sie verschiedene Blumen.Jede Blume hat einen Schönheitswert$A_{ichchchchchchchchchchchch}$。

Frau Lu ist der Meinung, dass ein schöner Garten einzigartig sein sollte, das heißt, er ist einzigartig $N-1$ Der Schönheitswert gepflanzter Blumen ist nur derselbe$1$ Der Schönheitswert gepflanzter Blumen unterscheidet sich von dem anderer Blumen.

Für jede Operation kann Miss Lu eine Blume auswählen und deren Schönheitswert steigern. $1$ oder minus$1$。

Nun möchte Frau Lu wissen, wie viele Eingriffe nötig sind, um den Garten einzigartig zu machen.

Eingabeformat

Die erste Zeile enthält eine positive Ganzzahl $N$, was die Länge des Gartens angibt.

Die zweite Zeile enthält $N$ positive ganze Zahl$A_1,A_2,\dots ,A_N$, was den Schönheitswert jeder Blume angibt.

Ausgabeformat

Gibt eine Ganzzahl aus, die die Mindestanzahl an Vorgängen darstellt, die erforderlich sind, um den Garten einzigartig zu machen.

Beispieleingabe

4
1 2 3 4
1
2

Beispielausgabe

2
1

Datenreichweite

• $1\le N\le 10^5$
• $1\le A_{ichchchchchchchchchchchch}\le 10^9$

Antwort

Die optimale Lösung besteht darin, zum Median zu werden und alle Kosten aufzuzählen, die für die Bildung des Medians anfallen.

Die Zeitkomplexität ist $Ö(N\mathrm{sieheG}N)$, die Raumkomplexität ist $Ö(N)$。

Referenzcode

• Python

def main():
    n = int(input())
    w = list(map(int, input().split()))
    w.sort()
    if w[0] == w[n - 1]:
        print("1")
        return
    s1, s2 = 0, 0
    m1, m2 = w[(n - 1) // 2], w[(n + 1) // 2]
    for i in range(n - 1):
        s1 += abs(m1 - w[i])
    for i in range(1, n):
        s2 += abs(m2 - w[i])
    print(min(s1, s2))

if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++)
            w[i] = scanner.nextInt();
        Arrays.sort(w);
        if (w[0] == w[n - 1]) {
            System.out.println("1");
            return;
        }
        long s1 = 0, s2 = 0;
        int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
        for (int i = 0; i < n - 1; i++)
            s1 += Math.abs(m1 - w[i]);
        for (int i = 1; i < n; i++)
            s2 += Math.abs(m2 - w[i]);
        System.out.println(Math.min(s1, s2));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100010;

int main() {
    int n, w[N];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];
    sort(w, w + n);
    if (w[0] == w[n - 1]) {
        cout << "1" << endl;
        return 0;
    }
    ll s1 = 0, s2 = 0;
    int m1 = w[(n - 1) / 2], m2 = w[(n + 1) / 2];
    for (int i = 0; i < n - 1; i++)
        s1 += abs(m1 - w[i]);
    for (int i = 1; i < n; i++)
        s2 += abs(m2 - w[i]);
    cout << min(s1, s2) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

🥝 04.LYA的字符画

Beschreibung der Frage

LYA ist seit kurzem besessen von der Charaktermalerei. Sie glaubt, dass die Schönheit einer Charaktermalerei gleich der Anzahl aufeinanderfolgender identischer Symbole in der Charaktermalerei ist.Beispielsweise ist die Ästhetik des Charaktergemäldes „aabbccddef“.$6$。

LYAs Freundin gab ihr eine $0$ Und$1$ LYA, die vom Zeichnen von Charakteren besessen ist, möchte alle Zeichenketten kennen, aus denen diese Zeichenkette besteht.TeilzeichenfolgeWas ist die Summe der Ästhetik?

Hinweis: Es gibt $C_{N+1}^2$ Teilzeichenfolge.

Eingabeformat

Geben Sie in der ersten Zeile eine positive Ganzzahl ein $N$, was die Länge der Zeichenfolge angibt.

Die Länge der zweiten Zeile beträgt $N$ von$01$ Zeichenfolge.

Ausgabeformat

Geben Sie eine Ganzzahl aus, die die Summe der Ästhetik aller Teilzeichenfolgen darstellt.

Beispieleingabe

4
0011
1
2

Beispielausgabe

14
1

Datenreichweite

$1\le N\le 2\times 10^5$

Antwort

Dieses Problem kann durch die Idee der Präfixsumme gelöst werden.

Zuerst können wir die Gesamtzahl der Teilzeichenfolgen der Zeichenfolge berechnen $\frac{N(N+1)}{2}$。

Dann iterieren wir über die Zeichenfolge und verwenden die Variablen $m$ Notieren Sie die Startposition der aktuell aufeinanderfolgenden identischen Symbole, variabel$R$ Aktuellen Standort aufzeichnen.Wann$S[R]\ne S[R-1]$ Wenn , bedeutet dies, dass ein neues Symbol erscheint und wir berechnen können$[m,R)$ Die Anzahl der Teilzeichenfolgen im Intervall$\frac{(R-m)(R-m+1)}{2}$, subtrahieren Sie es von der Gesamtzahl der Teilzeichenfolgen.

Übrig bleibt schließlich die Anzahl aller schönen Teilstrings, die ausgegeben werden können.

Zeitkomplexität $Ö(N)$, Raumkomplexität $Ö(1)$。

Referenzcode

• Python

def cal(length):
    return length * (length + 1) // 2

n = int(input())
s = input() + '#'

ans = 0
total = cal(n)
l = 0
for r in range(1, n + 1):
    if s[r] != s[r - 1]:
        ans += total - cal(l) - cal(n - r)
        l = r

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next() + "#";
        
        long ans = 0;
        long total = cal(n);
        int l = 0;
        for (int r = 1; r <= n; r++) {
            if (s.charAt(r) != s.charAt(r - 1)) {
                ans += total - cal(l) - cal(n - r);
                l = r;
            }
        }
        System.out.println(ans);
    }
    
    private static long cal(int len) {
        return (long) len * (len + 1) / 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• Cpp

#include <iostream>
#include <string>

using namespace std;

using ll = long long;

ll cal(int len) {
    return (ll) len * (len + 1) / 2;
}

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s += "#";
    
    ll ans = 0;
    ll total = cal(n);
    int l = 0;
    for (int r = 1; r <= n; r++) {
        if (s[r] != s[r - 1]) {
            ans += total - cal(l) - cal(n - r);
            l = r;
        }
    }
    cout << ans << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

🌸 05.卢小姐的数组删除计划

Fragename

Problembeschreibung

Miss Lu hat einen sehr großen Plan: Sie möchte alle Arrays auf der Welt löschen! Ihre Fähigkeit ist jedoch begrenzt, jedes Mal nur zwei identische Elemente im Array auszuwählen und alle Elemente dazwischen (einschließlich der beiden Elemente selbst) zu löschen.

Jetzt liegt vor Miss Lu eine Länge von $N$ Anordnung von$A$, möchte sie wissen, wie viele Elemente in diesem Array sie maximal löschen kann.

Eingabeformat

Die erste Zeile enthält eine positive Ganzzahl $N$, stellt ein Array dar $A$ Länge.

Die zweite Zeile enthält $N$ Durch Leerzeichen getrennte positive ganze Zahlen$A_1,A_2,\dots ,A_N$, stellt ein Array dar $A$ Elemente.

Ausgabeformat

Geben Sie eine Ganzzahl aus, die die maximale Anzahl von Elementen angibt, die Miss Lu löschen kann.

Beispieleingabe

4
1 2 1 2
1
2

Beispielausgabe

1
1

Datenreichweite

• $1\le N\le 2\times 10^5$
• $1\le A_{ichchchchchchchchchchchch}\le 10^9$

Antwort

Dieses Problem kann mit den Ideen der Sortierung und des Doppelzeigers gelöst werden.

Zuerst können wir das Array konvertieren $A$ Die Elemente in werden nach Wert sortiert und die ursprüngliche Position jedes Elements im Array wird aufgezeichnet. Der Zweck besteht darin, uns das Ermitteln des Positionsbereichs desselben Elements zu erleichtern.

Als nächstes können wir das sortierte Array durchlaufen und für jedes Element den Positionsbereich aller Elemente ermitteln, die denselben Wert haben $[M,R]$ . Elemente in diesem Bereich können gelöscht werden, da sie sich zwischen zwei identischen Elementen im ursprünglichen Array befinden.Wir können die Reichweite berechnen$[M,R]$ Die Anzahl der Elemente in$R-M-1$, vergleichen Sie es mit der aktuellen maximalen Anzahl gelöschter Elemente und aktualisieren Sie den Maximalwert.

Geben Sie abschließend die maximale Anzahl gelöschter Elemente aus.

Die Zeitkomplexität ist $Ö(N\mathrm{sieheG}N)$ , hauptsächlich die zeitliche Komplexität der Sortierung.Die Raumkomplexität ist$Ö(N)$, wird zum Speichern der ursprünglichen Position des Elements verwendet.

Referenzcode

• Python

n = int(input())
a = list(map(int, input().split()))

idx = sorted(range(n), key=lambda x: a[x])

ans = 0
i = 0
while i < n:
    j = i
    L, R = n, -1
    while j < n and a[idx[j]] == a[idx[i]]:
        L = min(L, idx[j])
        R = max(R, idx[j])
        j += 1
    ans = max(ans, R - L - 1)
    i = j

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Integer[] idx = new Integer[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            idx[i] = i;
        }

        Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));

        int ans = 0;
        for (int i = 0; i < n;) {
            int j = i;
            int L = n, R = -1;
            while (j < n && a[idx[j]] == a[idx[i]]) {
                L = Math.min(L, idx[j]);
                R = Math.max(R, idx[j]);
                j++;
            }
            ans = Math.max(ans, R - L - 1);
            i = j;
        }

        System.out.println(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> idx(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        idx[i] = i;
    }

    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return a[i] < a[j];
    });

    int ans = 0;
    for (int i = 0; i < n;) {
        int j = i;
        int L = n, R = -1;
        while (j < n && a[idx[j]] == a[idx[i]]) {
            L = min(L, idx[j]);
            R = max(R, idx[j]);
            j++;
        }
        ans = max(ans, R - L - 1);
        i = j;
    }

    cout << ans << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

schreibe am Ende

Hier möchte ich Ihnen die Check-in-Kabine für Senioren im Herbst empfehlen. Sie führt Sie Schritt für Schritt durch die Lösung häufiger schriftlicher Internet-Testfragen. Jeder Tag ist voller nützlicher Informationen.

🎧 秋招陪伴刷题打卡

• Probelesung:

[Herbst-Rekrutierungs-Check-in] Tag 01 – Angepasste Sortierung – CSDN-Blog

[Herbst-Rekrutierungs-Check-in] Tag 02 – Die stärkste zweiteilige Serie – Binäre Suche – CSDN-Blog

[Herbst-Rekrutierungs-Check-in] Tag 03 – Die stärkste Zwei-Punkte-Serie – Zwei-Punkte-Antwort – CSDN-Blog

Wir bieten Online-Rezensionen zu echten Fragen früherer großer Hersteller. Interessierte Freunde können eine private Nachricht an Qinglong senden, um mehr zu erfahren.

Und mehr! Und mehr! außerdem!

✈️ Eine umfassende Zusammenfassung schriftlicher Testfragen