poj3061 (Fußmessmethode)-javaLernprogramm-php.cn

Folge

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14927		Accepted: 6312

Zeitlimit: 1000MS

Speicherlimit: 65536K

Einreichungen insgesamt: 14927

Akzeptiert: 6312

Beschreibung

Eine Folge von N positiven ganzen Zahlen (10 < N < 100.000), von denen jede kleiner oder gleich 10.000 ist, und einer positiven ganzen Zahl S (S < 100.000.000) werden angegeben . Schreiben Sie ein Programm, um die minimale Länge der Teilfolge aufeinanderfolgender Elemente der Folge zu ermitteln, deren Summe größer oder gleich S ist.

Eingabe

<span style="font-size: 18px"><strong>2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5</strong></span>

Nach dem Login kopieren

Die erste Zeile ist die Anzahl der Testfälle. Für jeden Testfall muss das Programm die durch ein Intervall getrennten Zahlen N und S aus der ersten Zeile lesen. Die Nummern der Sequenz werden in der zweiten Zeile des Testfalls durch Intervalle getrennt angegeben. Die Eingabe wird mit dem Ende der Datei abgeschlossen.

<span style="font-size: 18px"><strong>2
3</strong></span>

Nach dem Login kopieren

Ausgabe

Für jeden Fall muss das Programm das Ergebnis in einer separaten Zeile der Ausgabedatei drucken. Wenn keine Antwort, drucken Sie 0.

Beispieleingabe

Beispielausgabe

Quelle

Südosteuropa 2006

<span style="color: #0000ff">import</span><span style="color: #000000"> java.util.Scanner;

</span><span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{

    </span><span style="color: #008000">/**</span><span style="color: #008000">
     * </span><span style="color: #808080">@param</span><span style="color: #008000"> args
     </span><span style="color: #008000">*/</span>
    <span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span><span style="color: #000000"> n,s;
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> map[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> sum[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args) {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        Scanner scan=<span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
        </span><span style="color: #0000ff">int</span> t=<span style="color: #000000">scan.nextInt();
        </span><span style="color: #0000ff">while</span>(t>0<span style="color: #000000">){
            n</span>=<span style="color: #000000">scan.nextInt();
            s</span>=<span style="color: #000000">scan.nextInt();
            </span><span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i=0;i<n;i++<span style="color: #000000">){
                map[i]</span>=<span style="color: #000000">scan.nextInt();
            }
            sovle();
            t</span>--<span style="color: #000000">;
        }
        
    }
    </span><span style="color: #0000ff">private</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> sovle() {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        <span style="color: #0000ff">int</span> res=n+1<span style="color: #000000">;
        </span><span style="color: #0000ff">int</span> ss=0,t=0,sum=0<span style="color: #000000">;
        </span><span style="color: #0000ff">for</span><span style="color: #000000">(;;){
            </span><span style="color: #0000ff">while</span>(t<n&&sum<<span style="color: #000000">s){
                sum</span>+=map[t++<span style="color: #000000">];
            }
            </span><span style="color: #0000ff">if</span>(sum<<span style="color: #000000">s){
                </span><span style="color: #0000ff">break</span><span style="color: #000000">;
            }
            res</span>=Math.min(res, t-<span style="color: #000000">ss);
            sum</span>-=map[ss++<span style="color: #000000">];
        }
        </span><span style="color: #0000ff">if</span>(res><span style="color: #000000">n){
            res</span>=0<span style="color: #000000">;
        }
        System.out.println(res);
    }

}</span>

Nach dem Login kopieren

算法设计：代码

Das obige ist der detaillierte Inhalt vonpoj3061 (Fußmessmethode). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten：

poj3061 取法

Quelle：php.cn

Vorheriger Artikel：Übersicht über den Kalender Nächster Artikel：Erste Schritte mit JSP-Grundlagen

Erklärung dieser Website

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Neueste Artikel des Autors