[ad_1]
Je suis tombé sur cette question :
Les vaches du fermier John ont la dent sucrée, et elles aiment particulièrement manger des cannes de bonbon ! FJ a N vaches au total, chacune avec une certaine taille initiale et il veut leur donner M cannes de bonbon, chacune également de hauteur variable (1≤N, M≤2⋅10^5).
FJ prévoit de donner les cannes de bonbon une par une aux vaches, dans l’ordre indiqué lors de l’entrée. Pour donner une canne en bonbon à ses vaches, il suspendra la canne en bonbon de manière à ce qu’au départ, la canne en bonbon touche juste le sol. Les vaches vont alors s’aligner une à une, dans l’ordre donné par l’entrée, et monter jusqu’à la canne en bonbon, chacune mangeant à hauteur (puisqu’elles ne peuvent pas atteindre plus haut). La canne en bonbon reste suspendue à l’endroit où elle est initialement installée et n’est pas abaissée au sol, même après que les vaches aient mangé le bas de la canne en bonbon. Il est possible qu’une vache ne mange rien pendant son tour, si la base de la canne en bonbon est déjà au-dessus de la taille de cette vache. Après que chaque vache ait eu son tour, les vaches grandissent en fonction du nombre d’unités de canne en bonbon qu’elles ont mangées, et le fermier John accroche la canne en bonbon suivante et les vaches répètent le processus à nouveau (la vache 1 étant à nouveau la première à commencer à manger la canne en bonbon). prochaine canne en bonbon). Note spéciale : La canne en bonbon flotte dans les airs, par exemple lorsqu’une vache d’une hauteur de 2 atteint une canne en bonbon d’une hauteur de 3, elle mange les 2 unités (1 et 2), et la 3ème unité de la canne en bonbon flotte toujours dans les airs, donc seules les vaches d’une taille ≥ 2 peuvent l’atteindre et le manger.
FORMAT D’ENTRÉE (pipe stdin) :
La première ligne contient N et M.
La ligne suivante contient les hauteurs initiales des Ncows, chacune dans la plage [1,10^9].
La ligne suivante contient les hauteurs des cannes de bonbon M, chacune dans la gamme [1,10^9].
FORMAT DE SORTIE (sortie standard du tuyau) :
Les hauteurs finales de chacune des N vaches sur des lignes distinctes.
Notez que la grande taille des entiers impliqués dans ce problème peut nécessiter l’utilisation de types de données entiers de 64 bits (par exemple, un “long long” en C/C++).
EXEMPLE D’ENTRÉE :
3 2
3 2 5
6 1
EXEMPLE DE SORTIE :
7
2
7 Explication :
La première canne en bonbon mesure 6 unités.
1. La première vache mange la portion de la première canne en bonbon jusqu’à la hauteur 3, après quoi la portion restante de la première canne en bonbon occupe les hauteurs [3,6].
2. La deuxième vache n’est pas assez grande pour manger le reste de la première canne en bonbon.
3. La troisième vache mange deux unités supplémentaires de la première canne en bonbon. La partie restante de la première canne en bonbon, occupant des hauteurs [5,6]ne se mange pas.
Ensuite, chaque vache grandit en fonction de la quantité qu’elle a mangée, de sorte que la taille des vaches devient [3+3,2+0,5+2]=[6,2,7].
La deuxième canne en bonbon mesure 1 unité de hauteur et la première vache la mange entièrement.
NOTATION :
* Entrées 2-10 : N,M≤10^3
* Entrées 11-14 : Aucune contrainte supplémentaire.
Et voici ma réponse C++ :
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n,m; cin>>n>>m; ll heightcow[n]; for(int i=1;i<=n;i++){ cin>>heightcow[i]; } ll finalcow[n]; for(ll i=1;i<=n;i++){ finalcow[i]=heightcow[i]; } ll heightcane[m]; for(ll i=1;i<=m;i++){ cin>>heightcane[i]; } for(ll j=1;j<=m;j++){//cane bool statcane[m]; for(ll i=1;i<=heightcane[j];i++){ statcane[i]=true; } for(ll i=1;i<=n;i++){//cow for(ll k=1;k<=heightcow[i];k++){ if(statcane[k]==true){ statcane[k]=false; finalcow[i]++; } } } } for(ll i=1;i<=n;i++){ cout<<finalcow[i]<<endl; } return 0; }
Ce que j’ai essayé :
Je ne sais pas quoi faire, je suis débutant. S’il vous plaît, aidez-moi !
Solution 1
La première chose que vous remarquez dans le code est que les index s’étendent au-delà de la fin des tableaux :
ll heightcow[n] = { 3, 2, 5 }; ll heightcane[m] = { 6, 1 }; ll finalcow[n]; for (ll i = 1; i <= n; i++) { //<- error!! finalcow[i] = heightcow[i]; }
Les tableaux commencent toujours à 0 et se terminent à n-1.
//modifier:
Je n’ai aucune explication pour laquelle un code MLE est demandé ici. La tâche demande un code d’alimentation séquentiel simple qui calcule la taille des vaches après avoir mangé des cannes de bonbon :
for (ll j = 0; j < m; j++) { ll lower_height = 0; ll upper_height = heightcane[j]; for (ll i = 0; i < n && lower_height < upper_height; i++) { if (finalcow[i] >= lower_height) { ll eaten = max((ll)0, min(finalcow[i], upper_height) - lower_height); finalcow[i] += eaten; lower_height += eaten; // new lower height } } }
[ad_2]
コメント